DS.zip_site:www.pudn.com

#include "stdio.h" #include "stdlib.h"//需要调用malloc函数 #define TRUE 1 #define FALES 0 #define OK 1 #define ERROR 0 #define INREASIBLE -1 #define OVERFLOW -2 #define MAXSIZE 1000 typedef int Status; //2.1 链表的实现与操作 struct NdList { int data; struct NdList *next; };//单链表存储结构实现 P28 Status InitList_L (struct NdList *L) { L->data = 0; L->next = NULL; }//单链表的初始化 头节点data存表长(元素个数) (自建） Status InsertList_L (struct NdList *L, int i, int e) { struct NdList *p = L; struct NdList *n; int j =0; while (p != NULL && j < i-1) { p = p->next; j ++; } if (p == NULL || j > i-1) return ERROR; n = (struct NdList *) malloc (sizeof(struct NdList)); n->data = e; n->next = p->next; p->next = n; L->data ++; return OK; }//单链表的插入: 将e插入单链表L中第i个元素前 P30 算法2.9 Status ScanList_L (struct NdList *L) { int e,i = 1; printf("\nplease input the nums to the list\n\n"); scanf ("%d",&e); while (e != 0) { InsertList_L (L,i,e); scanf ("%d",&e); i ++; } printf("\n"); }//键盘顺序输入元素到空单链表L中 输入0结束 (自建) 类似于算法2.11 Status PrintList_L (struct NdList *L) { struct NdList *p = L->next; while (p != NULL) { printf("%d ",p->data); p = p->next; } printf("\n"); printf("length = %d\n\n",L->data); }//顺序打印出单链表中各元素和单链表长度(元素个数) (自建) Status GetElem_L (struct NdList L,int i,int *e) { struct NdList *p = &L; int j = 0; while (p != NULL && j < i) { p = p->next; j ++; } if (p == NULL || j > i) return ERROR; *e = p->data; return OK; }//得到单链表中第i个元素放入e中 若i=0 则e为单链表长度 P29 算法2.8 Status DeleteList_L(struct NdList *L,int i,int *e) { struct NdList *p = L; int j = 0; while (p != NULL && j < i-1) { p = p->next; j ++; } if (p == NULL || j > i-1) return ERROR; struct NdList *q; q = p->next; p->next = q->next; *e = q->data; free (q); L->data --; }//删除单链表中第i个元素 并将其值放入e中 P30 算法2.10 Status DeleteList_elem(struct NdList *L,int k) { struct NdList *p,*q; p = L; while(p->next) { if(p->next->data==k) { q=p->next; p->next=q->next; free(q); } else p=p->next; } }//删除链表中元素数据为k的元素；自建 Status MergeList_L (struct NdList *L1,struct NdList *L2,struct NdList *L3) { struct NdList *La = L1->next,*Lb = L2->next,*Lc = L3; while (La != NULL && Lb != NULL) { if (La->data <= Lb->data) { Lc->next = La; La = La->next; } else { Lc->next = Lb; Lb = Lb->next; } Lc = Lc->next; } if (La != NULL) Lc->next = La; if (Lb != NULL) Lc->next = Lb; L3->data = L1->data + L2->data; }//升序合并两个升序序列L1、L2到L3中 P31 算法2.12 /**************************************************/ /**************************************************/ /**************************************************/ /**************************************************/ struct SLink { int data; int cur; };//单链表静态存储实现 P31 Status InitList_Sl (struct SLink *L) { int i; L[0].data = 0; L[0].cur = 0; for (i = 1;i < MAXSIZE;i++) L[i].cur = -1; }//静态单链表的的初始化 头结点data储存链长 P33 算法2.14 Status InsertList_Sl (struct SLink *L,int i,int e) { int j = 0,k = 0,m = 0; if (i > L[0].data+1 || j >= i) return ERROR; while (L[j].cur != -1) { j ++; } while (m < i-1) { k = L[k].cur; m ++; } L[j].data = e; L[j].cur = L[k].cur; L[k].cur = j; L[0].data ++; }//在静态存储的单链表L中第i元素之前插入e (自建) Status ScanList_Sl (struct SLink *L) { printf("\nplease input the nums to the list\n\n"); int e,i = 1; scanf("%d",&e); while (e != 0) { InsertList_Sl (L,i,e); scanf("%d",&e); ++ i; } printf("\n"); }//键盘顺序输入元素到静态存储的单链表L中 输入0结束 (自建) Status PrintList_Sl (struct SLink *L) { int i = 0; while (L[i].cur != -1 && L[i].cur != 0) { i = L[i].cur; printf("%d ",L[i].data); } printf("\nlength = %d\n\n",L[0].data); }//顺序打印出静态单链表中各元素和单链表长度(元素个数) (自建) Status DeleteList_Sl (struct SLink *L,int i,int *e) { int j = 0,m = 0,k; if (i > L[0].data || i <= 0) return ERROR; while (L[j].cur != -1 && m < i-1) { j = L[j].cur; m ++; } k =L[j].cur; L[j].cur = L[k].cur; L[k].cur = -1; *e = L[k].data; L[0].data --; }//删除静态单链表中第i个元素 并将其值放入e中 (自建) Status GetElem_Sl (struct SLink *L,int i,int *e) { int j = 0,m = 0; if (i > L[0].data || i <= 0) return ERROR; while (L[j].cur != -1 && m < i) { j = L[j].cur; m ++; } *e = L[j].data; }//得到静态单链表中第i个元素放入e中 (自建) Status LocateList_Sl (struct SLink *L,int i,int *e) { int j = 0,k = 0; while (L[j].cur != 0) { k ++; j = L[j].cur; if (L[j].data == i) *e = k; } if (L[j].cur == 0) return FALES; } void DelElem(struct SLink *L,int e) { int i,j=0; i=L[0].cur; while(L[i].cur!=0) { if(L[i].data!=e) { j=i; i=L[i].cur; } else { L[j].cur=L[i].cur; i=j; L[0].data--; } } }////删除L中所有元素数据为e的元素 自建 void ChangeElem1(struct SLink *L,int e) { int i,j=0; i=L[0].cur; while(L[i].cur!=0) { if(L[i].data!=e) { j=i; i=L[i].cur; } else { L[j].cur=L[i].cur; L[i].cur=L[0].cur; L[0].cur=i; i=j; } } }//将L中所有元素数据为e的元素放在最前 自建 void ChangeElem2(struct SLink *L,int e) { int fw=-1,w=-1,p=-1,fm=-1,wm=-1; p=L[0].cur; while(p!=0) { if(L[p].data!=e) { if (fw==-1) {fw=p;fm=p;} else { L[fm].cur=p; fm=p; } } else { if (w==-1) {w=p;wm=p;} else { L[wm].cur=p; wm=p; } } p=L[p].cur; } L[0].cur=fw; L[wm].cur=0; L[fm].cur=w; }//将L中所有元素数据为e的元素放在最后 自建 main(void) { //2.2 链表的实现与操作测试 int e; struct NdList L1; InitList_L (&L1); ScanList_L (&L1); PrintList_L (&L1); GetElem_L (L1,5,&e); printf("%d\n\n",e); DeleteList_L (&L1,2,&e); PrintList_L (&L1); printf("%d\n\n",e); //测试单链表: Init,Insert,Scan,Print,Delete; struct NdList L2,L3,L4; InitList_L (&L2); InitList_L (&L3); InitList_L (&L4); ScanList_L (&L2); PrintList_L (&L2); ScanList_L (&L3); PrintList_L (&L3); MergeList_L (&L2,&L3,&L4); PrintList_L (&L4); //测试单链表: Merge; /**************************************************/ /**************************************************/ /**************************************************/ /**************************************************/ int e1; struct SLink L5[MAXSIZE]; InitList_Sl (L5); ScanList_Sl (L5); PrintList_Sl (L5); InsertList_Sl (L5,3,45); PrintList_Sl (L5); DeleteList_Sl (L5,2,&e1); PrintList_Sl (L5); printf("%d\n\n",e1); InsertList_Sl (L5,4,135); PrintList_Sl (L5); printf("%d\n\n",L5[2].data);//测试在delete函数中删除时释放的结点是否被使用 GetElem_Sl (L5,5,&e1); printf("%d\n\n",e1); LocateList_Sl (L5,9,&e1); printf("%d\n\n",e1); //测试静态单链表相关