摘要：
visit_ printf）；Lb）；20List_插入；compare_ Elem）；Lb）；visit_ printf）；4142列表_删除（&；val_1）；4445清除列表（&；
1、每个代码都是博主一个字一个敲出来的（有参考，但是我很认真的去分析了每个函数逻辑结构，并做了一定的修改）
2、函数都已经通过测试，没有bug，符合要求
3、这里只贴出代码，代码里有些本人的理解和注释，但是没有那么详细
代码分为
main.c
1 #include <stdio.h> 2 #include "fuction.h" 3 4 int main(void){ 5 Sqlist La; 6 Sqlist Lb; 7 Sqlist Lc; 8 int i=0; 9 int val_1 ; 10 Init_List( &La ); 11 List_Insert(&La, 1, 1); 12 List_Insert( &La, 2, 5 ); 13 List_Insert( &La, 3, 8 ); 14 List_Insert( &La, 4, 11 ); 15 List_Traverse( La, visit_printf ); 16 Init_List( &Lb ); 17 List_Insert( &Lb, 1, 2 ); 18 List_Insert( &Lb, 2, 6 ); 19 List_Insert( &Lb, 3, 8 ); 20 List_Insert( &Lb, 4, 9 ); 21 List_Insert( &Lb, 5, 11 ); 22 List_Insert( &Lb, 6, 15 ); 23 List_Insert( &Lb, 7, 20 ); 24 List_Traverse( Lb, visit_printf ); 25 Init_List( &Lc ); 26 Merge_List( La, Lb, &Lc ); 27 printf("单个输出="); 28 visit_printf(Lc.pBase); 29 printf(" "); 30 List_Traverse( Lc, visit_printf); 31 i = Locate_Elem( La, 8, compare_Elem); 32 printf("位序=%d ", i); 33 34 Union(&La,Lb); 35 List_Traverse( La, visit_printf); 36 37 Prior_Elem( La, 5, &val_1) ; //当定义int *val_1 = 0 时候，作为实参进入却没发生错误。 38 printf("前驱=%d ", val_1); //因为 指针初始化时指向一块不能读写的内存，一般为0X00000000 39 Next_Elem( La, 5, &val_1) ; //如果对其进行操作，会发生错误 40 printf("前驱=%d ", val_1); 41 42 List_Delete(&La,2,&val_1); 43 printf("删除=%d ", val_1); 44 45 Clear_List(&Lc); 46 i = List_Length(Lc); 47 printf("1---%d ", i); 48 Destroy_List(&Lc); 49 i = List_Length(Lc); 50 printf("2---%d ", i); 51 if( List_Empty(Lc) ) 52 printf("表是空的 "); 53 54 return 0; 55 }
list_declaration.h
1 #ifndef LIST_DECLARATION 2 #define LIST_DECLARATION 3 #define TURE 1 4 #define FALSE 0 5 #define ERROR 0 6 #define OVERFLOW -2 7 #define MAX_SIZE 100 //初始化分配给线性表的长度，单位为(struct List) 8 #define ADD_SIZE 10 //线性表每次存储空间增长的长度，单位为(struct List) 9 #define ElemType int 10 typedef int Status; 11 typedef struct List{ 12 int *pBase; //分配给线性表的存储空间的首地址 13 int cnt; //线性表的使用长度 14 int len; //线性表的最大长度 15 }Sqlist,*pSqlist; 16 17 #endif //LIST_DECLARATION
fuction.h
1 /* 2 所有函数已经全通过测试，没有BUG 3 */ 4 5 #include "list_declaration.h" 6 #ifndef FUCTION_H 7 #define FUCTION_H 8 //构造一个使用长度为空的线性表L 9 int Init_List( Sqlist *L ); 10 //初始条件：若线性表L已存在；操作结果：销毁线性表L 11 int Destroy_List( Sqlist *L ); 12 //初始条件：若线性表L已存在；操作结果：把线性表置为空表 13 int Clear_List( Sqlist *L ); 14 //初始条件：若线性表L已存在；操作结果：若L为空表返回TURE,否则返回FALSE 15 int List_Empty( Sqlist L ); 16 //初始条件：若线性表L已存在；操作结果：返回L中数据元素个数 17 int List_Length( Sqlist L ); 18 //初始条件：若线性表L已存在,1<=pos<=len(L)；操作结果：用e返回L中第pos个元素的值 19 int Get_Elem( Sqlist L, int pos, int *e ); 20 //初始条件：若线性表L已存在，compare()是数据元素判定函数 21 //操作结果：返回L中第1个与e满足关系compare()的数据元素的位序，若这样的数据元素不存在，则返回值为0 22 int Locate_Elem( Sqlist L, int pos, int (*compare)( int , int ) ); 23 //初始条件：若线性表L已存在； 24 //操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义 25 int Prior_Elem( Sqlist L, int cur_e, int *pre_e ); 26 //初始条件：若线性表L已存在； 27 //操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回它的前驱，否则操作失败，next_e无定义 28 int Next_Elem( Sqlist L, int cur_e, int *next_e ); 29 //初始条件：若线性表L已存在,1<=pos<=len(L)+1； ？？？ 30 //操作结果：在L中第pos个位置之前插入新都数据元素e，L都长度加1 31 int List_Insert( Sqlist *L, int pos, int e ); 32 //初始条件：若线性表L已存在,1<=pos<=len(L)； 33 //操作结果：删除L第pos个数据元素，并用e返回其值，L都长度减1 34 int List_Delete( Sqlist *L, int pos, int *e ); 35 //初始条件：线性表L已存在 36 //操作结果：依次对L都每个数据元素调用函数visit()。一旦visit()失败，则操作失败 37 int List_Traverse( Sqlist L, void (*visit)( int* ) ); 38 //输出地址e所指向内存的值 39 void visit_printf( int *e ); 40 //将存在于Lb中而不在La中的数据插入到La中去 41 void Union(Sqlist *La, Sqlist Lb); 42 //比较a，b的大小，若相等则返回1，否则返回0 43 int compare_Elem(int a, int b); 44 //初始条件：已知顺序线性表La和Lb的元素按值非递减排列 45 //操作结果:归并La和Lb得到新的线性表Lc,Lc的元素也按值非递减排列 46 void Merge_List(Sqlist La, Sqlist Lb,Sqlist *Lc); 47 48 #endif //FUCTION_H
fuction.c
1 /* 每个函数根据实际情况是否要返回值，制定返回值所对应的含义，一般不要中止整个程序的运行 */ 2 /* 代码里各个函数 关于Sqlist L 还是 Sqlist *L的选用问题 */ 3 /* Sqlist L: 多用于不需要改变L里面的变量，只需要调用它们的值 */ 4 /* Sqlist *L: 多用于需要改变L里面的变量的值 */ 5 /* 这么做的原因是可以更直观的表现一种思想，而如果不怕麻烦。可以运用 * 来解决这个问题，本质上无差别 */ 6 #include <stdio.h> 7 #include <stdlib.h> 8 #include <malloc.h> 9 #include "fuction.h" 10 11 int compare_Elem(int a, int b){ 12 if( a == b) 13 return TURE; 14 else 15 return FALSE; 16 } 17 void visit_printf( int *e ){ 18 printf("%d ", *e ); 19 } 20 int Init_List( Sqlist *L ){ //malloc()分配成功返回首地址，否则返回NULL 21 L->pBase = ( int* )malloc( sizeof(int) * MAX_SIZE ); 22 if( !L->pBase ) exit(OVERFLOW); //分配失败 23 L->cnt = 0; 24 L->len = MAX_SIZE; 25 return TURE; 26 } 27 int Destroy_List( Sqlist *L ){ 28 free(L->pBase); //free(L->pBase)后，一定要L->pBase=NULL。以防出现野指针 29 L->pBase = NULL; //当L->pBase=NULL后，无论free()多少次都没关系，否则2次会导致程序运行错误 30 L->cnt = 0; 31 L->len = 0; 32 return TURE; 33 } 34 int Clear_List( Sqlist *L ){ 35 L->cnt = 0; 36 return TURE; 37 } 38 int List_Empty( Sqlist L ){ 39 if( L.cnt == 0 ) 40 return TURE; 41 else 42 return FALSE; 43 } 44 int List_Length( Sqlist L ){ 45 return L.cnt; 46 } 47 int Get_Elem( Sqlist L, int pos, int *e ){ 48 if( pos < 1 || pos > L.cnt ) //return()是返回函数调用，从当前函数调用返回到主函数继续执行 49 exit(ERROR); //exit() 表示退出当前进程/当前程序；不再执行 50 *e = *(L.pBase+pos-1); //或 *e = L.pBase[pos-1] ; 51 return TURE; 52 } 53 int Locate_Elem(Sqlist L, int e, int (*compare)( int , int )){//这个函数需要重点掌握，涉及到函数指针相关知识 54 int i = 1; 55 int *p = L.pBase; 56 while( i <= L.cnt && !compare( *p++, e ) ) i++; 57 if( i <= L.cnt ) 58 return i; 59 else 60 return 0; 61 } 62 int Prior_Elem( Sqlist L, int cur_e, int *pre_e ){ 63 int i = 2; 64 int *p = L.pBase + 1; 65 while( i <= L.cnt && *p != cur_e ){ // 2 至 cnt， 依次比较 66 p++; 67 i++; 68 } 69 if( i > L.cnt ) 70 return FALSE; 71 else{ 72 *pre_e = *--p; //前驱 73 return TURE; 74 } 75 } 76 int Next_Elem( Sqlist L, int cur_e, int *next_e ){ 77 int i=1; 78 int *p = L.pBase; 79 while( i < L.cnt && *p != cur_e ){ //1至cnt-1 依次比较 80 i++; 81 p++; 82 } 83 if( i == L.cnt ) 84 return FALSE; 85 else{ 86 *next_e = *++p; //后驱 87 return TURE; 88 } 89 } 90 int List_Insert( Sqlist *L, int pos, int e ){ 91 92 int i; 93 if( pos <1 || pos > L->len + 1 ) //这个L->len + 1 表示可以在表尾插入（追加） 94 return ERROR; 95 if (L->cnt >= L->len) { // 96 int* newBase = (int *) realloc(L->pBase,(L->len + ADD_SIZE) * sizeof(int)); 97 if (!newBase) { 98 printf("分配内存单元失败"); 99 return 0; 100 } 101 L->pBase = newBase; 102 L->len += ADD_SIZE; 103 } 104 for( i = L->cnt ; i >= pos; i-- ) 105 L->pBase[i+1] = L->pBase[i]; 106 L->pBase[i] = e; //插入e 107 L->cnt++; //使用长度加1 108 return TURE; 109 } 110 int List_Delete( Sqlist *L, int pos, int *e ){ 111 int i = 0; 112 *e = L->pBase[pos-1]; 113 if( pos > 1 && pos < L->cnt ){ 114 for( i = pos; i < L->cnt; i++ ){ 115 L->pBase[i] = L->pBase[i+1]; 116 } 117 L->cnt--; 118 return TURE; 119 } 120 else 121 return ERROR; //pos 值不合法 122 } 123 int List_Traverse( Sqlist L, void (*vi)( int* ) ){ 124 int *p; //这个函数里面的第三个参数是一个指向函数的函数指针vi。而它所指向的函数 125 int i; //这里只是对函数指针的声明，因此参数只需要给出数据类型就好 126 p = L.pBase; 127 for( i = 1; i <= L.cnt; i++){ //因为每个函数都有一个入口函数，就是函数名，有了函数名就可以调用函数 128 // 等价于vi(p++); //函数入口 与 函数之间 有调用机制（这个不管，知道有这回事就好） 129 (*vi)(p++); // vi 指向 visit_pritnf(入口函数)的首地址 130 } // 1、*vi 相当于取得 visit_pritnf 首地址; 2、vi = visit_pritnf 131 printf(" "); //第一种是取地址，第二种是直接赋地址，因此是等效的 132 return TURE; 133 } 134 void Union(Sqlist *La, Sqlist Lb){ 135 int i; 136 int e; 137 int La_cnt; 138 int Lb_cnt; 139 La_cnt = List_Length(*La); Lb_cnt = List_Length(Lb); //求线性表的长度 140 for( i = 1; i <= Lb_cnt; i++ ){ //遍历并获取Lb中的元素 141 Get_Elem( Lb, i, &e ); 142 if( !Locate_Elem( *La, e, compare_Elem ) ) //La中不存在等于e的元素 143 List_Insert( La,++La_cnt, e ); //把这个e插入到La中 144 } 145 } 146 void Merge_List(Sqlist La, Sqlist Lb,Sqlist *Lc){ 147 //La和Lb已经存在的 148 int i = 1, j = 1, k = 0; 149 int ai,bi; 150 La.len = List_Length(La); //获取La表使用长度 151 Lb.len = List_Length(Lb); //获取Lb表使用长度 152 Init_List(Lc); 153 while( ( i <= La.len ) && ( j <= Lb.len ) ){ 154 Get_Elem( La, i, &ai ); Get_Elem( Lb, j, &bi ); //获取La和Lb的元素 155 if( ai <= bi ) { List_Insert( Lc, ++k, ai ); ++i; } //比较获取的元素，然后插入 156 else { List_Insert( Lc, ++k, bi ); ++j; } 157 } 158 while( i <= La.len ){//当La和Lb中任何一方提前全部插入，如不存在，则第一个循环就可以解决了 159 Get_Elem( La, i++, &ai ); List_Insert( Lc, ++k, ai ); 160 } 161 while( j <= Lb.len ){ 162 Get_Elem( Lb, j++, &bi ); List_Insert( Lc, ++k, bi ); 163 } 164 }