《单链表数据结构C语言》由会员分享，可在线阅读，更多相关《单链表数据结构C语言（9页珍藏版）》请在金锄头文库上搜索。
1、单链表的建立（头插法）写一算法用头插法建立无头结点的单链表，结果返回单链表的头指针typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList CreateListF(void)char ch;LinkList head;ListNode *s;head=NULL;ch=getchar();while(ch!=n)s=(ListNode*)malloc(sizeof(ListNode);s-data=ch;s-next=h
2、ead;head=s;ch=getchar();return(head);单链表的打印写一算法打印不带头结点的单链表head中每个结点的值typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void PrintList(LinkList head)ListNode *p;for(p=head;p;p=p-next) printf(%c,p-data);printf(n);单链表的建立（尾插法）写一算法用尾插法建立无头结点的单链表，
3、结果返回单链表的头指针typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList CreateListR(void)char ch;LinkList head;ListNode *s,*r;head=NULL;r=NULL;while (ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);s-data=ch;if (head=NULL) head=s;else r-
4、next=s;r=s;if (r!=NULL) r-next=NULL;return(head);单链表的建立（尾插法）写一算法用尾插法建立带头结点的单链表，结果返回单链表的头指针typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList CreateListR1(void)char ch;LinkList head=(ListNode *)malloc(sizeof(ListNode);ListNode *s,*r;r
5、=head;while (ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);s-data=ch;r-next=s;r=s;r-next=NULL;return(head);单链表的打印写一算法打印带头结点的单链表head中每个结点的值typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;voidPrintList(LinkList head)ListNode *p;for(p
6、=head-next;p;p=p-next) printf(%c,p-data);printf(n);单链表的查找写一算法在带头结点的单链表head中查找第i个结点typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList GetNode(LinkList head,int i)int j;ListNode *p;p=head;j=0;while (p-next & jnext;j+;if (i=j) return(p)
7、;else return(NULL);单链表的查找写一算法在带头结点的单链表head中查找其值为key的结点typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList LocateNode(LinkList head,DataType key)ListNode *p=head-next;while (p&p-data!=key) p=p-next;return(p);单链表的插入写一算法将值为x的新结点插入到带头结点的单
8、链表head的第i个结点的位置上typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void InsertList(LinkList head,DataType x,int i)ListNode *p,*s;p=GetNode(head,i-1);/寻找第i-1个结点if(p=NULL)printf(插入位置非法n);exit(0);s=(ListNode *)malloc(sizeof(ListNode);s-data=x;s-
9、next=p-next;p-next=s;2单链表的删除写一算法删除带头结点的单链表中的第i个结点typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void DeleteList(LinkList head,int i)ListNode *p,*r;p=GetNode(head,i-1);/寻找第i-1个结点if(p=NULL|p-next=NULL)printf(删除位置非法n);exit(0);r=p-next;p-next
10、=r-next;free(r);2单链表的逆置试用单链表作为存储结构，实现线性表(a0,a1,an-1)就地逆置的操作，所谓“就地”指辅助空间应为O(1)typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void InverseList(LinkList *head)ListNode *p,*t,*h;h=(*head)-next;p=h-next;h=(*head)-next;h-next=NULL;while(p!=NULL
11、)t=p-next;p-next=h;h=p;p=t;(*head)-next=h;2单链表的长度在带头结点的单链表上实现线性表的ListLength(L)运算typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;int ListLength(LinkList L)int i=0;ListNode *p;for(p=L-next;p;p=p-next) i+;return(i);2单链表的长度在不带头结点的单链表上实现线性表的Lis
12、tLength(L)运算typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;int ListLength(LinkList L)int i=0;ListNode *p;for(p=L;p;p=p-next) i+;return(i);2有序单链表的插入设单链表L是一个递减有序表，试写一算法将x插入其中后仍保持L的有序性（从头结点开始搜寻适当的插入位置，然后插入）typedef char DataType;typedef struc
13、t nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void InsertSortList(LinkList *L, DataType x)LinkNode *p,*s;p=*L;if (p=NULL | x=p-data)s=(ListNode *)malloc(sizeof(ListNode);s-data=x;s-next=p;*L=s;elsewhile (p-next!=NULL & xnext-data)p=p-next;s=(ListNode *)malloc(sizeof(ListN
14、ode);s-data=x;s-next=p-next;p-next=s;2有序单链表的插入设单链表L是一个递减有序表，试写一算法将x插入其中后仍保持L的有序性（先把x插入链表头，然后通过交换移动到正确的位置）typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void InsertSortList(LinkList *L, DataType x)LinkNode *p,*s;DataType t;s=(ListNode *)malloc(sizeof(ListNode);s-data=x;s-next=*L;*L
