单向链表小实验

野性酷女 2022-04-04 06:40 118阅读 0赞

### *转自* [http://blog.sina.com.cn/s/blog\_8882eb010102vz35.html][http_blog.sina.com.cn_s_blog_8882eb010102vz35.html]*本人于(*2015-08-21 14:33:34*)创作，无法实现搬迁，只能重新粘贴。* ###

上篇博客说过下一篇会写makefile或者配置文件构造，结果夭折了，发现短时间还摘不出来，那就算了吧，先把以前写的小东西整好，不然又都忘了。今天重新看了一下，整理出来。

我会把程序全部贴上，直接gcc就能通过，方便学习。整套的基础是我以前学习的时候从其他博客能代码粘过来的。很久了，貌似也没改变什么。

这些接口就是为了了解什么是链表，链表怎么构建和使用。实际使用比这个要健壮很多，抛砖引玉。

链表是什么呢，其实很简单，链表就是存储同一类数据的一个链，像珍珠项链一样，一个疙瘩一个疙瘩的，不过这个项链没有连接成一个圈。每个疙瘩习惯上叫做节点。节点的内容实际就是指针，一个指向你想保存的数据类型的一个指针。找到这个指针，就找到了它锁连接这的那段内存空间。操作节点，只需知道头就OK了，链表的结尾一个节点指向的下一个节点一般为NULL。

链表就是上一段总结的这么个东西。每个节点指向的内存空间除了想要保存的数据外，这个空间里还有指针，还是指向这种内存段空间的指针。单向链表呢就有一个指针，指向下一个节点，双向链表呢有两个指针，一个指向前一个节点，一个指向后一个节点。哈哈，就说道这里，精髓自己体会~~~![单向链表小实验][E_6725EN00SIGG.gif]

下面是代码，编译的是这串指令:gcc -o node1 node1.c，我保存在node1.c文件中了。

\#include  
\#include

struct grade  
\{  
int score;//sizeof(int)=4  
struct grade \*next;//sizeof(next)=8  
\};  
typedef struct grade NODE;//sizeof(NODE)=16

NODE \*Create();  
void Insert(NODE \*head, NODE \*pnew, int i);  
void Delete(NODE \*head, int i);  
void Display(NODE \*head);  
void Destroy(NODE \*head);

int main(void)  
\{  
NODE \*head, \*pnew;

//创建链表并显示。  
head = Create();  
if(NULL == head)  
\{  
printf("head is null.\\n");  
return 0;  
\}  
Display(head);  
return 0;  
//插入的新数据。值和位置。  
pnew = (NODE \*)malloc(sizeof(NODE));//pnew->score=0,malloc也会清0  
if(NULL == pnew)  
\{  
printf("chuang jian shi bai!\\n");  
return 0;  
\}  
pnew->score = 444;  
Insert(head, pnew, 3);

//显示插入后的链表。  
printf("cha ru hou de lian biao:\\n");  
Display(head);

//显示删除后的链表。  
Delete(head, 2);  
printf("shan chu hou de lian biao:\\n");  
Display(head);

//销毁链表。  
Destroy(head);  
return 0;  
\}

NODE \*Create()  
\{  
printf("\*\*\*\*\*\*\*\*\*\*\*Create start\*\*\*\*\*\*\*\*\*\*\\n");  
NODE \*head, \*tail, \*pnew;//sizeof(head)=8  
int score;  
head = (NODE \*)malloc(sizeof(NODE));//sizeof(NODE)=16  
if(NULL == head)  
\{  
printf("Create failed!\\n");  
return NULL;  
\}  
head->score = 88888888;  
head->next = NULL;  
tail = head;//tail必不可少，让head和创建的节点相关联，就这个作用。  
printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n"  
"\*head = %p \\n"  
"\*head->score = %d \\n"  
"\*head->next = %p \\n",  
head, head->score, head->next);  
printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n"  
"\*The score < 0 means stop.\*\\n"  
"\* Put in scores: \*\\n"  
"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");  
while(1)  
\{  
scanf("%d", &score);  
if(0 > score)  
\{  
printf("score < 0, create end.\\n");  
break;  
\}  
pnew = (NODE \*)malloc(sizeof(NODE));  
if(NULL == pnew)  
\{  
printf("chuang jian shi bai.\\n");  
return NULL;  
\}  
pnew->score = score;  
pnew->next = NULL;//保证链表中最后一个节点的指针域为空。  
tail->next = pnew;//tail是活动的，总是指向表中最后一个节点。开始时指向head，之后指向pnew。tail此时指向pnew之前开的那个pnew，这一步让之前的那个pnew的指针域指向新的pnew。  
tail = pnew;//tail向后移动，指向新的pnew。  
printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n"  
"new node = %p next = %p score = %d\\n"  
"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n",  
pnew, pnew->next, pnew->score);  
\}  
printf("\*\*\*\*\*\*\*\*\*\*\*Create end\*\*\*\*\*\*\*\*\*\*\\n");  
return head;  
\}

void Insert(NODE \*head, NODE \*pnew, int i)//插入到i的后面，从1开始数。  
\{  
printf("\*\*\*\*\*\*\*\*\*\*Insert start\*\*\*\*\*\*\*\*\*\*\*\\n");  
NODE \*p;  
int j;

p = head;  
for(j = 0; j < i && p != NULL; j++)  
\{  
p = p->next;  
\}  
if(NULL == p)  
\{  
printf("The node is not alive.\\n");  
return;  
\}  
pnew->next = p->next;  
p->next = pnew;  
printf("\*\*\*\*\*\*\*\*\*\*Insert end\*\*\*\*\*\*\*\*\*\*\*\\n");  
\}

void Delete(NODE \*head, int i)  
\{  
printf("\*\*\*\*\*\*\*\*\*\*\*\*delete start\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");  
NODE \*p, \*q;  
int j;  
if(0 == i)//节点号从1开始。  
\{  
printf("Number is i = 0, from 1.\\n");  
return;  
\}

p = head;  
for(j = 1; j < i && p->next != NULL; j++)//j=1,删除第n个，j=0，删除第n+1个  
\{  
printf("j=%d p=%p p->next=%p\\n", j, p, p->next);  
p = p->next;  
printf("j=%d p=%p p->next=%p\\n", j, p, p->next);  
\}  
if(NULL == p->next)  
\{  
printf("bu cun zai.\\n");  
return;  
\}

q = p->next;  
p->next = q->next;  
free(q);  
printf("\*\*\*\*\*\*\*\*\*\*\*\*delete end\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");  
\}

void Display(NODE \*head)  
\{  
printf("\*\*\*\*\*\*\*\*\*\*\*\*display start\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");  
NODE \*p;  
for(p = head; p != NULL; p = p->next)  
\{  
printf("p=%p, next=%p, score=%d\\n", p, p->next, p->score);  
\}  
printf("\*\*\*\*\*\*\*\*\*\*\*\*display end\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");  
\}

void Destroy(NODE \*head)  
\{  
printf("\*\*\*\*\*\*\*\*\*\*\*\*destroy start\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");  
NODE \*p, \*q;  
p = head;  
while(NULL != p->next)  
\{  
q = p->next;  
p->next = q->next;  
free(q);  
\}  
free(p);//释放head  
printf("\*\*\*\*\*\*\*\*\*\*\*\*destroy end\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");  
\}

新浪博客写程序博客真不方便！！！！！！太傻了！！！！

这个代码直接贴出去就能编译通过，对于理解链表很不错。就到这里了。博客会坚持下去的

[http_blog.sina.com.cn_s_blog_8882eb010102vz35.html]: http://blog.sina.com.cn/s/blog_8882eb010102vz35.html
[E_6725EN00SIGG.gif]: /images/20220404/6387994a7e4146899e3987ea6df69d06.png