数据结构（C语言版）.docx

《数据结构（C语言版）.docx》由会员分享，可在线阅读，更多相关《数据结构（C语言版）.docx（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C语言经典(C语言必看文档)数据结构C语言实现系列1一一线性表#include #include typedef int elemType;/*以下是关于线性表顺序存储操作的16种算法 */* struct List elemType *list;int size; int maxSize;）；void againMalloc(struct List *L) (/*空间扩展为原来的2倍，并由p指针所指向，原内容被自动拷贝到p所指向的存储空间*/ elemType *p = realloc (L-listr 2 * L-maxSize * sizeof(elemType);if (!p) /*分

2、配失败则退出运行*/printf (存储空间分配失败！)； exit(1);1L-list = p; /*使list指向新线性表空间*/L-maxSize = 2 * L-maxSize; /*把线性表空间大小修改为新的长度*/ )/* 1.初始化线性表L,即进行动态存储空间分配并置L为一个空表*/ void initList(struct List *LZ int ms) (/*检查ms是否有效，若无效的则退出运行*/ if(ms maxSize = ms; /设置线性表空间大小为ms */ L-size = 0; L-list = malloc(ms * sizeof(elemType);

3、 if(!L-list)printf (空间分配失败！”)；exit (1);return; /* 2 .清除线性表L中的所有元素，释放存储空间，使之成为一个空表*/ void clearList(struct List *L) (if(L-list != NULL)free (L-list);L-list = 0;L-size = L-maxSize = 0; | return;/* 3 .返回线性表L当前的长度，若L为空则返回0 */ int sizeList(struct List *L) (return L-size; /* 4 .判定线性表L是否为空，若为空则返回1,否则返回0 */

4、 int emptyList(struct List *L) (if(L-size =0) return 1;)else return 0; ) )/* 5 .返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行*/ elemType getElem(struct List *L, int pos) (if (pos L-size) /若 pos 越界则退出运行 */printf (元素序号越界！);exit(1); return L-list pos - 1 ;/*返回线性表中序号为pos值的元素值*/* 6.顺序扫描(即遍历)输出线性表L中的每个元素*/ void trave

5、rseList(struct List *L)int i;for(i = 0; i size; i+) printf (*%d ”, L -list i); printf(M M); return;/* 7 .从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1 */ int findList(struct List L, elemType x) ( int i;for(i = 0; i size; i+)if (L-listi = x) return i;) return -1;)/* 8 .把线性表L中第pos个元素的值修改为x的值，若修改成功返回1,否则返回0 */ i

6、nt updatePosList(struct List *LZ int pos, elemType x) (if (pos L-size) /* 若 pos 越界则修改失败 */return 0;L-listpos - 1 = x; return 1; /* 9 .向线性表L的表头插入元素x */ void inserFirstList(struct List *L, elemType x) ( int i;if(L-size = L-maxSize) againMalloc(L); for(i = L-size - 1; i = 0; i-)L-listi + 1 = L -listi;

7、L-list0 = x; L-size +; return;/* 10 .向线性表L的表尾插入元素x */ void insertLastList(struct List *L, elemType x) ( if (L-size = L -maxSize) /*重新分配更大的存储空间*/againMalloc(L);L-list L-size = x; /* 把 x 插入到表尾 */L-size+; /*线性表的长度增加1 */ return; )/ 11 .向线性表L中第pos个元素位置插入元素x,若插入成功返回1,否则返回0 */ int insertPosList(struct List

8、 *LZ int pos, elemType x) ( int i;if (pos L-size + 1) /* 若 pos 越界则插入失败 */return 0;) if (L-size = L-maxSize) /*重新分配更大的存储空间*/againMalloc(L);) for (i = L-size - 1; i = pos - 1; i) L-listi + 1 = L-listi;L-listpos - 1 = x; L-size+; return 1; ) /* 12 .向有序线性表L中插入元素x,使得插入后仍然有序*/ void insertOrderList(struct

9、List *LZ elemType x) ( int iz j;/*若数组空间用完则重新分配更大的存储空间*/ if(L-size = L-maxSize) againMalloc(L);/*顺序查找出X的插入位置*/ for(i = 0; i size; i+) if (x listi) break;) /*从表尾到下标i元素依次后移一个位置，把i的位置空出来*/ for (j = L-size - 1; j = i; j )L-listj+1 = L-listj；/*把x值赋给下标为i的元素*/L-listi = x;/*线性表长度增加1 */L-size+;return; /* 13 .

10、从线性表L中删除表头元素并返回它，若删除失败则停止程序运行*/ elemType deleteFirstList(struct List *L) (elemType temp;int i;if(L -size = 0)printf (线性表为空，不能进行删除操作！);exit(1); temp = L-list0; for(i = 1; i size; i+)L-listi-l = L-listi;L-size-;return temp; )/* 14 .从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行*/ elemType deleteLastList(struct List *L

11、) (if(L -size = 0)printf (”线性表为空，不能进行删除操作！ exit(1);L-size-;return L -list L-size;/*返回原来表尾元素的值*/* 15.从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行*/ elemType deletePosList(struct List *LZ int pos) (elemType temp;int i;if (pos L-size) /* pos 越界则删除失败 */printf (pos值越界，不能进行删除操作！ n);exit(1);temp = L-listpos-1;for(i =

12、pos; i size; i+) L-listi-1 = L-listi;L-size; return temp;/* 16 .从线性表L中删除值为x的第一个元素，若成功返回1,失败返回0 */ int deleteValueList(struct List *LZ elemType x) (int 1, j;/从线性表中顺序查找出值为x的第一个元素*/for(i = 0; i size; i+)if (L-listi = x) break;) )/*若查找失败，表明不存在值为x的元素，返回0 */if(i = L-size) return 0;/*删除值为x的元素i */for(j = i

13、+ 1; j size; j+) L-listj-1 = L-listj;L-size;return 1; void main() (int a10 = 2, 4, 6, 8, 10, 12, 14, 16, 18, 20);int i;struct List L;initList(&L, 5);for(i = 0; i 10; i+) insertLastList(&Lr ai);insertPosList(&LZ 11r 48);insertPosList(&LZ 1, 64);printf(n%d ”， getElem(&L, 1);traverseList(&L);printf(n%d

14、 ”, findList(&LZ 10);updatePosList(&LZ 3, 20);printf(n%d ”, getElem(&Lf 3);traverseList(&L);deleteFirstList(&L);deleteFirstList(&L);deleteLastList(&L);deletePosList(&LZ 7);deleteLastList(&L);deletePosList(&LZ 5);printf(H%d ”, sizeList(&L);printf(H%d , emptyList(&L); traverseList(&L);clearList(&L);re

15、turn 0;#include #include #define NN 12#define MM 20typedef int elemType ;/Hr*/*以下是关于线性表链接存储(单链表)操作的16种算法*/struct sNode/*定义单链表结点类型*/elemType data;struct sNode *next;； / 1 .初始化线性表，即置单链表的表头指针为空*/ void initList(struct sNode* *hl) (*hl = NULL;return; /* 2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表*/ void clearL

16、ist(struct sNode* *hl) (/* cp和np分别作为指向两个相邻结点的指针*/struct sNode *cpz *np;cp = *hl;/*遍历单链表，依次释放每个结点*/while(cp != NULL)np = cp-next; /*保存下个结点的指针*/ free(cp);cp = np; *hl = NULL;/*置单链表的表头指针为空*/return;/* 3.返回单链表的长度*/int sizeList(struct sNode *hl) (int count = 0;/*用于统计结点的个数*/while(hl != NULL) count+;hl = hl

17、-next; return count; )/* 4 .检查单链表是否为空，若为空则返回1,否则返回0 */ int emptyList(struct sNode *hl) (if(hl = NULL) return 1;else return 0;) )/* 5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行*/ elemType getElem(struct sNode *hlf int pos) (int i = 0;/*统计已遍历的结点个数*/if (pos next;if (hl != NULL) return hl-data;elseprintf (pos值非

18、法，退出运行！);exit(1);)/* 6.遍历一个单链表/ void traverseList(struct sNode *hl) (while (hl != NULL) printf(n%5dH, hl-data); hl = hl-next;)printf(H n); return;)/* 7 .从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */ elemType* findList(struct sNode *hl, elemType x) (while(hl != NULL) if (hl-data = x) return &

19、hl-data;else hl = hl-next;) return NULL;)/* 8 .把单链表中第pos个结点的值修改为x的值，若修改成功返回1,否则返回0 */ int updatePosList(struct sNode hl, int pos, elemType x) (int i = 0;struct sNode *p = hl;while (p != NULL) /* 查找第 pos 个结点 */i+； if(pos = i)break;else p = p-next;)if(pos = i) p-data = x; return 1;elsereturn 0;/* 9.向单

20、链表的表头插入一个元素*/void insertFirstList(struct sNode* *hl, elemType x)struct sNode *newP;newP = malloc(sizeof(struct sNode);if(newP = NULL)printf (”内存分配失败，退出运行！n)；exit(1);newP-data = x;/*把x的值赋给新结点的data域*/*把新结点作为新的表头结点插入*/newP-next = *hl;*hl = newP;return;/ 10 .向单链表的末尾添加一个元素*/void insertLastList(struct sNo

21、de* *hlr elemType x) (struct sNode *newP;newP = malloc(sizeof(struct sNode);if(newP = NULL)printf (”内在分配失败，退出运行！);exit(1);/*把X的值赋给新结点的data域，把空值赋给新结点的next域*/ newP-data = x;newP-next = NULL;/若原表为空，则作为表头结点插入*/if(*hl = NULL)*hl = newP;/*查找到表尾结点并完成插入*/else (struct sNode *p = NULL;while(p-next != NULL) p

22、= p-next;) p-next = newP;return;/* 11.向单链表中第pos个结点位置插入元素为X的结点，若插入成功返回1 ,否则返回0 */ int insetPosList(struct sNode* *hl, int pos, elemType x)int i = 0;struct sNode *newP;struct sNode *cp = *hl, *ap = NULL;/*对pos值小于等于0的情况进行处理*/if (pos next;)/*产生新结点，若分配失败，则停止插入*/newP = malloc(sizeof(struct sNode);if(newP

23、= NULL)printf (”内存分配失败，无法进行插入操作！”)；return 0;)/*把x的值赋给新结点的data域*/newP-data = x;/*把新结点插入到表头/if(ap = NULL) newP-next = cp;/* 或改为 newP-next = *hl; */*hl = newP;/*把新结点插入到ap和cp之间*/else (newP-next = cp; ap-next = newP;return 1;/*插入成功返回1 */* 12 .向有序单链表中插入元素x结点，使得插入后仍然有序*/ void insertOrderList(struct sNode*

24、*hlz elemType x)/*把单链表的表头指针赋给CP，把ap置空*/ struct sNode *cp = *hl, *ap = NULL;/*建立新结点*/struct sNode *newP;newP = malloc(sizeof(struct sNode);if (newP = NULL)printf (内在分配失败，退出运行！)； exit(1);newP-data = x;/*把x的值赋给新结点的data域*/*把新结点插入到表头*/if ( (cp = NULL) (x data) ) /*这个地方要注意呀*/ newP-next = cp;*hl = newP;ret

25、urn; /*顺序查找出x结点的插入位置*/while(cp != NULL)if (x data)break;else(ap = cp;cp = cp-next; /*把x结点插入到ap和cp之间*/newP-next = cp;ap-next = newP; return;)/* 13 .从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行*/ elemType deleteFirstList(struct sNode* *hl) (elemType temp;struct sNode *p = *hl;/*暂存表头结点指针，以便回收*/if(*hl = NULL)prin

26、tf (单链表为空，无表头可进行删除，退出运行！”)；exit(1); *hl = (*hl)-next;/*使表头指针指向第二个结点*/temp = p-data;/*暂存原表头元素，以便返回/free(p);return temp;/*回收被删除的表头结点*/*返回第个结点的值*/* 14 .从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行*/ elemType deleteLastList(struct sNode* *hl) (elemType temp;/*初始化cp和ap指针，使cp指向表头结点，使ap为空*/struct sNode *cp = *hl;struct

27、sNode *ap = NULL;/单链表为空则停止运行*/if(cp = NULL)printf (”单链表为空，无表头进行删除，退出运行！ ,); exit(1);/*从单链表中查找表尾结点，循环结束时cp指向表尾结点，ap指向其前驱结点*/ while(cp-next != NULL)ap = cp;cp = cp-next; )/*若单链表中只有一个结点，则需要修改表头指针*/if(ap = NULL)*hl = (*hl) -next;/* 或改为= NULL; */*删除表尾结点*/else (ap-next = NULL; /*暂存表尾元素，以便返回*/temp = cp-dat

28、a;free (cp) ;/回收被删除的表尾结点/return temp;/返回表尾结点的值 /* 15 .从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行*/ elemType deletePosList(struct sNode* *hlz int pos) (int i = 0;elemType temp;/初始化cp和ap指针，使cp指向表头结点，使ap为空*/struct sNode *cp = *hl;struct sNode *ap = NULL;/*单链表为空或pos值非法则停止运行*/if(cp = NULL) (pos next; )/*单链表中没有第po

29、s个结点*/if (cp = NULL) printf (pos值不正确，退出运行！ u);exit(1); /*若pos等于1,则需要删除表头结点*/if(pos = 1)*hl = (*hl) -next;/* 或改为*hl = cp-next; */否则删除非表头结点，此时cp指向该结点，ap指向前驱结点/else ap-next = cp-next; )/*暂存第pos个结点的值，以便返回*/temp = cp-data;free (cp) ;/*回收被删除的第pos个结点*/return temp; /*返回在temp中暂存的第pos个结点的值*/ /* 16.从单链表中删除值为x的

30、第一个结点，若删除成功则返回1,否则返回0 */ int deleteValueList(struct sNode* *hl, elemType x) (/*初始化cp和ap指针，使cp指向表头结点，使ap为空*/struct sNode *cp = *hl;struct sNode *ap = NULL;/*从单链表中查找值为X的结点，找到后由cp指向该结点，由ap指向其前驱结点/ while(cp != NULL)if(cp-data = x)break;ap = cp;cp = cp-next;/*若查找失败，即该单链表中不存在值为x的结点，则返回0 */if(cp = NULL) re

31、turn 0;)/*假如删除的是表头或非表头结点则分别进行处理*/if(ap = NULL)*hl = (*hl) -next;/* 或改为*hl= cp-next */elseap-next = cp-next;free(cp) ;/*回收被删除的结点*/return 1;/*返回1表示删除成功*/int main(int argc, char* argv)(int aNN;int i;struct sNode *p, *h, *s;srand(time(NULL);initList(&p);for(i = 0; i NN; i+) ai = rand() & MM;)printf (随机数

32、序列：”)；for(i = 0; i NN; i+) printf(H%5dnz ai);printf(M n);printf (“随机数逆序：“);for(i = 0; i next)while(deleteValueList(&(h-next), h-data)printf(去除重复数：“);traverseList(p);printf (单链表长度：%5d , sizeList (p);h = NULL;for(s = p; s != NULL; s = s-next) insertOrderList(&h, s-data);)printf (有序表序列：，)；traverseList(

33、h);clearList(&p);system(npausen);return 0;数据结构C语言实现系列2 一栈#include #include typedef int elemType;/*以下是关于栈顺序存储操作的6种算法*/struct stackelemType *stack;/*存储栈元素的数组指针*/int top;/*存储栈顶元素的下标位置/int maxSize;/*存储stack数组的长度*/；void againMalloc(struct stack *s)(/*空间扩展为原来的2倍，原内容被自动拷贝到p所指向的存储空间中/ elemType *p;p = reallo

34、c(s-stackr 2 * s-maxSize * sizeof(elemType); if(!p)printf (”内在分配失败！ ”);exit(1);/*把栈空间的大小修改新的长度*/s-stack = p;/*使stack指向新的栈空间*/s-maxSize = 2 * s-maxSize; return;/* 1.初始化栈S为空*/ void initStack(struct stack s, int ms) ( if(ms maxSize = ms;s-stack = malloc(ms * (sizeof(elemType); if (!s-stack)printf (”内在分

35、配失败！); exit(1);)s-top = -1;/*初始置栈为空*/return;)/* 2.新元素进栈，即把它插入到栈顶*/ void push(struct stack *s, elemType x) (/*若栈空间用尽则重新分配更大的存储空间*/ if (s-top = s-maxSize - 1) againMalloc(s);)s-top+;/栈顶指针后移一个位置*/s-stack s-top = x;/*将新元索插入到栈顶*/return;)/* 3 .删除(弹出)栈顶元素并返回其值*/ elemType pop(struct stack *s) (/*若栈空则退出运行*/i

36、f(s-top = -1) printf (栈空，无元素出栈！ ”)； exit (1);)s-top；/*栈顶指针减1表示出栈*/return s-stack s-top+l;/* 返回原栈顶元素的值 */* 4.读取栈顶元素的值*/elemType peek(struct stack *s)/*若栈空则退出运行*/if (s-top = -1) printf (栈空，无元素可读取！”)；exit (1);)return s-stacks-top ;/返回原栈顶元素的值*/* 5.判断s是否为空，若是则返回1表示其，否则返回0表示假*/ int emptyStack(struct stack

37、 *s) (if (s-top = -1)return 1;else(return 0;/* 6.清除栈s中的所有元素，释放动态存储空间*/ void clearStack(struct stack *s) (if (s-stack)free(s-stack);s-stack = NULL;s-top = -1;s-maxSize = 0;return;int main()(struct stack s;int a8 = 3, 8, 5, 17, 9, 30, 15, 22);int i;initStack(&s, 5);for(i = 0; i data = x;/*给新分配的结点赋值*/*

38、向栈顶插入新结点*/ newP-next = *hs;*hs = newP;return; /* 3 .从链栈中删除一个元素并返回它(出栈) elemType pop(struct sNode* *hs)struct sNode *p;elemType temp;if (*hs = NULL) printf (栈空无法删除！); exit (1);)/*暂存栈顶结点指针，并使栈顶指针指向下一个结点*/ p = *hs;*hs = p-next;/*暂存原栈顶元素以便返回，同时回收原栈顶结点*/ temp = p-data;free(p);return temp;/*返【可原栈顶元素*/* 4

39、.读取栈顶元素*/elemType peek(struct sNode* *hs) (/*对于空栈则退出运行/if(*hs = NULL) printf (栈空，无栈顶元素！); exit(1);)return (*hs) -data;/*返回栈顶结点的值*/* 5 .判断链栈是否为空，为空返回1,否则返回0 */ int emptyStack(struct sNode* *hs) (if(*hs = NULL) return 1;elsereturn 0; )/* 6.清除链栈为空*/void clearStack(struct sNode* *hs) (struct sNode *cp, *np;cp = *hs;/*使cp指向栈顶结点*/*从栈底依次删除每个结点*/ while(cp != NULL)