数据结构C语言实现系列[1]——线性表.doc

数据结构C语言实现系列1线性表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-list, 2 * L-maxSize * sizeof(elemType); if(!p) /* 分配失败则退出运行 */ printf(存储空间分配失败！ ); exit(1); L-list = p; /* 使list指向新线性表空间 */ L-maxSize = 2 * L-maxSize; /* 把线性表空间大小修改为新的长度 */* 1.初始化线性表L，即进行动态存储空间分配并置L为一个空表 */void initList(struct List *L, int ms) /* 检查ms是否有效，若无效的则退出运行 */ if(ms maxSize = ms; /* 设置线性表空间大小为ms */ L-size = 0; L-list = malloc(ms * sizeof(elemType); 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为空则返回 */int sizeList(struct List *L) return L-size;/* 4.判断线性表L是否为空，若为空则返回1, 否则返回0 */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-listpos - 1; /* 返回线性表中序号为pos值的元素值 */* 6.顺序扫描（即遍历）输出线性表L中的每个元素 */void traverseList(struct List *L) int i; for(i = 0; i size; i+) printf(%d , L -listi); printf( ); 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 */int updatePosList(struct List *L, 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; L-list0 = x; L-size +; return;/* 10.向线性表L的表尾插入元素x */void insertLastList(struct List *L, elemType x) if(L-size = L -maxSize) /* 重新分配更大的存储空间 */ againMalloc(L); L-listL-size = x; /* 把x插入到表尾 */ L-size+; /* 线性表的长度增加 */ return;/* 11.向线性表L中第pos个元素位置插入元素x，若插入成功返回，否则返回 */int insertPosList(struct List *L, 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 List *L, elemType x) int i, 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.从线性表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-1 = L-listi; L-size-; return temp;/* 14.从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行 */elemType deleteLastList(struct List *L) if(L -size = 0) printf(线性表为空，不能进行删除操作！ ); exit(1); L-size-; return L -listL-size; /* 返回原来表尾元素的值 */* 15.从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行 */elemType deletePosList(struct List *L, int pos) elemType temp; int i; if(pos L-size) /* pos越界则删除失败 */ printf(pos值越界，不能进行删除操作！ ); exit(1); temp = L-listpos-1; for(i = pos; i size; i+) L-listi-1 = L-listi; L-size-; return temp;/* 16.从线性表L中删除值为x的第一个元素，若成功返回1，失败返回0 */int deleteValueList(struct List *L, elemType x) int i, j; /* 从线性表中顺序查找出值为x的第一个元素 */ for(i = 0; i size; i+) if(L-listi = x) break; /* 若查找失败，表明不存在值为x的元素，返回0 */ if(i = L-size) return 0; /* 删除值为x的元素L-listi */ for(j = i + 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(&L, ai); insertPosList(&L, 11, 48); insertPosList(&L, 1, 64); printf(%d , getElem(&L, 1); traverseList(&L); printf(%d , findList(&L, 10); updatePosList(&L, 3, 20); printf(%d , getElem(&L, 3); traverseList(&L); deleteFirstList(&L); deleteFirstList(&L); deleteLastList(&L); deleteLastList(&L); deletePosList(&L, 5); ;deletePosList(&L, 7); printf(%d , sizeList(&L); printf(%d , emptyList(&L); traverseList(&L); clearList(&L); return 0;-修改过的 #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-list, 2 * L-maxSize * sizeof(elemType); if(!p) /* 分配失败则退出运行 */ printf(存储空间分配失败！ ); exit(1); L-list = p; /* 使list指向新线性表空间 */ L-maxSize = 2 * L-maxSize; /* 把线性表空间大小修改为新的长度 */* 1.初始化线性表L，即进行动态存储空间分配并置L为一个空表 */void initList(struct List *L, int ms) /* 检查ms是否有效，若无效的则退出运行 */ if(ms maxSize = ms; /* 设置线性表空间大小为ms */ L-size = 0; L-list = malloc(ms * sizeof(elemType); 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为空则返回 */int sizeList(struct List *L) return L-size;/* 4.判断线性表L是否为空，若为空则返回1, 否则返回0 */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-listpos - 1; /* 返回线性表中序号为pos值的元素值 */* 6.顺序扫描（即遍历）输出线性表L中的每个元素 */void traverseList(struct List *L) int i; for(i = 0; i size; i+) printf(%d , L -listi); printf( ); 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 */int updatePosList(struct List *L, 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; L-list0 = x; L-size +; return;/* 10.向线性表L的表尾插入元素x */void insertLastList(struct List *L, elemType x) if(L-size = L -maxSize) /* 重新分配更大的存储空间 */ againMalloc(L); L-listL-size = x; /* 把x插入到表尾 */ L-size+; /* 线性表的长度增加 */ return;/* 11.向线性表L中第pos个元素位置插入元素x，若插入成功返回，否则返回 */int insertPosList(struct List *L, 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 List *L, elemType x) int i, 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.从线性表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-1 = L-listi; L-size-; return temp;/* 14.从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行 */elemType deleteLastList(struct List *L) if(L -size = 0) printf(线性表为空，不能进行删除操作！ ); exit(1); L-size-; return L -listL-size; /* 返回原来表尾元素的值 */* 15.从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行 */elemType deletePosList(struct List *L, int pos) elemType temp; int i; if(pos L-size) /* pos越界则删除失败 */ printf(pos值越界，不能进行删除操作！ ); exit(1); temp = L-listpos-1; for(i = pos; i size; i+) L-listi-1 = L-listi; L-size-; return temp;/* 16.从线性表L中删除值为x的第一个元素，若成功返回1，失败返回0 */int deleteValueList(struct List *L, elemType x) int i, j; /* 从线性表中顺序查找出值为x的第一个元素 */ for(i = 0; i size; i+) if(L-listi = x) break; /* 若查找失败，表明不存在值为x的元素，返回0 */ if(i = L-size) return 0; /* 删除值为x的元素L-listi */ for(j = i + 1; j size; j+) L-listj-1 = L-listj; L-size-; return 1;/*/int 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(&L, ai); insertPosList(&L, 11, 48); insertPosList(&L, 1, 64); printf(%d , getElem(&L, 1); traverseList(&L); printf(%d , findList(&L, 10); updatePosList(&L, 3, 20); printf(%d , getElem(&L, 3); traverseList(&L); deleteFirstList(&L); deleteFirstList(&L); deleteLastList(&L); deleteLastList(&L); deletePosList(&L, 5); ;deletePosList(&L, 7); printf(%d , sizeList(&L); printf(%d , emptyList(&L); traverseList(&L); clearList(&L); system(pause); -/*顺序存储线性表的基本操作*/#include #define N 10 /*数组空间*/int sq_insert(int *,int *,int,int,int); /*插入元素*/int sq_delete(int *,int *,int); /*删除元素*/int main() int listN,i,n=N-1; /*n为线性表元素数*/ int x=100,pos=5; /*插入值与插入位置*/ for (i=0;in;i+) /*建立一个数组存储线性表*/ listi=i; for (i=0;in-1;i+) printf(%d,listi); printf(%dn,listi); if (sq_insert(list,&n,pos,N,x)!=0) printf(Error inserting elementn); else for(i=0;in-1;i+) printf(%d,listi); printf(%dn,listi); if (sq_delete(list,&n,pos)!=0) printf(Error deleting elementn); else for (i=0;in-1;i+) printf(%d,listi); printf(%dn,listi); int sq_insert(int *list,int *npt,int i,int maxn,int x) int k; if (i*npt) return 1; /*进行合理性检查*/ if (*npt=maxn) return 2; for (k=*npt;ki;k-) /*循环后移*/ listk=listk-1; listk=x; +*npt; return 0;int sq_delete(int *list,int *npt,int i) int v; if (i=*npt) return 1; if (*npt=0) return 2; for (v=i+1;v*npt;v+) /*循环前移*/ listv-1=listv; -*npt; system(pause); return 0; -数据结构C语言实现系列1线性表2#include #include #define NN 12#define MM 20typedef int elemType ;/*/* 以下是关于线性表链接存储（单链表）操作的16种算法 */*/struct sNode /* 定义单链表结点类型 */ elemType data; struct sNode *next;/* 1.初始化线性表，即置单链表的表头指针为空 */void initList(struct sNode* *hl) *hl = NULL; return;/* 2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */void clearList(struct sNode* *hl) /* cp和np分别作为指向两个相邻结点的指针 */ struct sNode *cp, *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-next; return count;/* 4.检查单链表是否为空，若为空则返回，否则返回 */int emptyList(struct sNode *hl) if(hl = NULL) return 1; else return 0; /* 5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */elemType getElem(struct sNode *hl, int pos) int i = 0; /* 统计已遍历的结点个数 */ if(pos next; if(hl != NULL) return hl-data; else printf(pos值非法，退出运行！ ); exit(1); /* 6.遍历一个单链表 */void traverseList(struct sNode *hl) while(hl != NULL) printf(%5d, hl-data); hl = hl-next; printf( ); return;/* 7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */elemType* findList(struct sNode *hl, elemType x) while(hl != NULL) if(hl-data = x) return &hl-data; else hl = hl-next; return NULL;/* 8.把单链表中第pos个结点的值修改为x的值，若修改成功返回，否则返回 */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; else return 0; /* 9.向单链表的表头插入一个元素 */void insertFirstList(struct sNode* *hl, elemType x) struct sNode *newP; newP = malloc(sizeof(struct sNode); if(newP = NULL) printf(内存分配失败，退出运行！ ); exit(1); newP-data = x; /* 把x的值赋给新结点的data域 */ /* 把新结点作为新的表头结点插入 */ newP-next = *hl; *hl = newP; return;/* 10.向单链表的末尾添加一个元素 */void insertLastList(struct sNode* *hl, 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 !=