回顾：动态分配和撤销内存
#include <stdio.h>
#include <malloc.h>
struct Student
{
int num;
float score;
struct Student *next;
};
int main( )
{
struct Student *p;
p=malloc(sizeof(struct Student));
p->num=31001;
p->score=89.5;
printf("%d %.1f\n", p->num, p->score);
free(p);
return 0;
}
遍历链表
void traverse(Node *h)
{
Node *p;
p = h; /*p指向头结点*/
while(p!=NULL)
{
printf("%-5d", p->data); /*“访问”结点，此处用最简单的操作：读取输出*/
p = p->next; /*p指向下一个结点，继续处理*/
}
printf("\n");
return;
}
创建一个链表
#include <stdio.h>
#include <malloc.h>
typedef struct NODE
{
int data;
struct NODE *next;
} Node;
Node *createLinkList(int n);
void traverse(Node *h);
int main( )
{
Node *head;
head = createLinkList(5);
traverse(head);
return 0;
}
Node *createLinkList(int n)
{
Node *h=NULL, *p, *last; /*h指向头结点，p指向新增结点，last指向尾结点*/
int d; /*用于输入要插入的元素的值*/
int i;
for(i=0; i<n; i++)
{
scanf("%d", &d);
p = (Node *)malloc(sizeof(Node)); /*p指向新增的结点*/
p->data = d; /*为数据域赋值*/
p->next = NULL; /*指针域为空*/
if (h==NULL) /*如果h==NULL为真，说明p为第一个结点，由h指向该结点*/
h = p;
else /*否则，原最后一个结点指向新增的结点，新结点加在链表尾*/
last->next = p;
last= p; /*last保持指向最后一个结点的角色*/
}
return h;
};
void traverse(Node *h)
{
Node *p;
p = h; /*p指向头结点*/
while(p!=NULL)
{
printf("%-5d", p->data); /*“访问”结点，此处用最简单的操作：读取输出*/
p = p->next; /*p指向下一个结点，继续处理*/
}
printf("\n");
return;
}
插入结点应用——建立有序链表
#include <stdio.h>
#include <malloc.h>
typedef struct NODE
{
int data;
struct NODE *next;
} Node;
Node *insertNode(Node *h, int b);
void traverse(Node *h);
int main( )
{
int b[]= {67, 25, 78, 99, 87},i;
Node *head=NULL;
for(i=0; i<5; i++)
head=insertNode(head, b[i]);
traverse(head);
return 0;
}
Node *insertNode(Node *h, int b)
{
Node *q1=h,*q2,*p;
p=(Node*)malloc(sizeof(Node)); /*生成新结点*/
p->data=b;
if(h==NULL) /*当前链表为空，p作为首结点*/
{
h=p; /*头结点就是p，将p赋值给h*/
p->next=NULL; /*p的指针域赋值为空，表示尚无下一个结点*/
}
else if(p->data<h->data) /*要插入的元素值小于首结点元素，插入结点作为首结点*/
{
h=p; /*将头结点h赋值为p*/
p->next=q1; /*p的下一个结点是原先的首结点（见q1的初始化，其值为h）*/
}
else /*在中间找到插入p的位置，将其插入*/
{
/*先找到合适的位置，q1的初值是h，即从头结点开始考察*/
while((q1!=NULL&&p->data>=q1->data))
{
q2=q1; /*q2记录q1的值*/
q1=q1->next; /*q1继续向后试探，直到a1*/
}
/*将新结点p插在q2后*/
p->next=q2->next; /*p的下一个结点为当前q2的下一结点，即p1*/
q2->next=p; /*q2的下一个结点y变为p，不再是q1*/
}
return h;
}
void traverse(Node *h)
{
Node *p;
p = h; /*p指向头结点*/
while(p!=NULL)
{
printf("%-5d", p->data); /*“访问”结点，此处用最简单的操作：读取输出*/
p = p->next; /*p指向下一个结点，继续处理*/
}
printf("\n");
return;
}
删结点应用——在有序表中删除
#include <stdio.h>
#include <malloc.h>
typedef struct NODE
{
int data;
struct NODE *next;
} Node;
Node *insertNode(Node *h, int b);
Node *deleteNode(Node *h, int b);
void traverse(Node *h);
int main( )
{
int b[]= {67, 25, 78, 99, 87},i;
Node *head=NULL;
for(i=0; i<5; i++)
head=insertNode(head, b[i]);
traverse(head);
head=deleteNode(head, 43);
traverse(head);
head=deleteNode(head, 78);
traverse(head);
return 0;
}
Node *insertNode(Node *h, int b)
{
Node *q1=h,*q2,*p;
p=(Node*)malloc(sizeof(Node)); /*生成新结点*/
p->data=b;
if(h==NULL) /*当前链表为空，p作为首结点*/
{
h=p; /*头结点就是p，将p赋值给h*/
p->next=NULL; /*p的指针域赋值为空，表示尚无下一个结点*/
}
else if(p->data<h->data) /*要插入的元素值小于首结点元素，插入结点作为首结点*/
{
h=p; /*将头结点h赋值为p*/
p->next=q1; /*p的下一个结点是原先的首结点（见q1的初始化，其值为h）*/
}
else /*在中间找到插入p的位置，将其插入*/
{
/*先找到合适的位置，q1的初值是h，即从头结点开始考察*/
while((q1!=NULL&&p->data>=q1->data))
{
q2=q1; /*q2记录q1的值*/
q1=q1->next; /*q1继续向后试探，直到a1*/
}
/*将新结点p插在q2后*/
p->next=q2->next; /*p的下一个结点为当前q2的下一结点，即p1*/
q2->next=p; /*q2的下一个结点y变为p，不再是q1*/
}
return h;
}
Node *deleteNode(Node *h, int b)
{
Node *p, *q;
p=h; /*p首先指向头结点*/
if(h==NULL) /*链表为空时不能删除*/
printf("List is null, delete fail.\n");
else
{
/*首先找到要删除的结点*/
while(b!=p->data&&p->next!=NULL)
{
q=p; /*q记录p的值*/
p=p->next; /*p接着指向下一个结点，q一直保持是p的上一个结点*/
}
if(b==p->data) /*要删除的结点p在链表中存在*/
{
if(p==h) /*要删除的结点就是头结点时，令h指向p的下一个结点即可*/
h = p->next;
else /*否则，删除q的下一个结点p*/
q->next = p->next;
free(p); /*释放p结点*/
}
else
printf("%d not found, delete fail.\n", b);
}
return h;
}
void traverse(Node *h)
{
Node *p;
p = h; /*p指向头结点*/
while(p!=NULL)
{
printf("%-5d", p->data); /*“访问”结点，此处用最简单的操作：读取输出*/
p = p->next; /*p指向下一个结点，继续处理*/
}
printf("\n");
return;
}
