c/c++语言开发共享线性表的链式存储

  1 #include <stdio.h>   2 #include <stdlib.h>   3 typedef int elemtype;   4    5 typedef struct lnode {   6     elemtype data;   7     struct lnode *next;   8 } linklist;   9   10 /*建立单链表*/  11 /*头插法*/  12 void createlistf(linklist* &l, elemtype a[], int n) {  13     l = (linklist *)malloc(sizeof(linklist));  14     l -> next = null;  15   16     int i;  17     linklist *s;  18     for(i = 0; i < n; i++) {  19         s = (linklist *)malloc(sizeof(linklist));  20         s -> data = a[i];  21         s -> next = l -> next;  22         l -> next = s;  23     }  24 }  25   26 /*尾插法*/  27 void createlistr(linklist* &l, elemtype a[], int n) {  28     l = (linklist *)malloc(sizeof(linklist));  29     l -> next = null;  30   31     linklist *p;//指针 p 来进行操作  32     p = l;  33   34     linklist *s;  35     int i;  36     for(i = 0; i < n; i++) {  37         s = (linklist *)malloc(sizeof(linklist));  38         s -> data = a[i];  39         p -> next = s;  40         p = s;  41     }  42     p -> next = null;  43 }  44   45 /*基本运算*/  46 /*初始化线性表 initlist(l)*/  47 void initlist(linklist* &l) {  48     l = (linklist *)malloc(sizeof(linklist));  49     l -> next = null;  50 }  51   52 /*销毁线性表 destorylist(l)*/  53 void destorylist(linklist* &l) {  54     linklist *pre = l;  55     linklist *p = l -> next;  56   57     while(p != null) {  58         free(pre);  59         pre = p;  60         p = p -> next;  61     }  62   63     free(pre);  64 }  65   66 /*判断线性表是否为空 listempty(l)*/  67 bool listempty(linklist* l) {  68     return l -> next == null;  69 }  70   71 /*求线性表的长度 listlength(l)*/  72 int listlength(linklist* l) {  73     linklist *p = l;  74     int i = 0;  75   76     while(p -> next != null) {  77         p = p -> next;  78         i++;  79     }  80   81     return i;  82 }  83   84 /*输出线性表 displist(l)*/  85 void displist(linklist* l) {  86     linklist *p = l -> next;  87   88     while(p != null) {  89         printf("%d ", p -> data);  90         p = p -> next;  91     }  92   93     printf("n");  94 }  95   96 /*求线性表中某个数据元素值 getelem(l, i, e)*/  97 bool getelem(linklist* l, int i, elemtype &e) {  98     linklist *p = l;  99  100     int k = 0; 101     while(k < i && p != null) { 102         k++; 103         p = p ->next; 104     } 105  106     if (p == null) { 107         return false; 108     } else { 109         e = p -> data; 110         return true; 111     } 112 } 113  114 /*按元素值查找 locateelem(l, e)*/ 115 int locateelem_wq(linklist* l, elemtype e) { 116     linklist *p = l; 117  118     int k = 0; 119     while(p != null) { 120         if (e == p -> data) { 121             return k; 122         } 123         p = p -> next; 124         k++; 125     } 126  127     return 0; 128 } 129  130 int locateelem(linklist* l, elemtype e) { 131     linklist *p = l -> next; 132  133     int k = 1; 134     while(p != null && e != p -> data) { 135         p = p -> next; 136         k++; 137     } 138  139     if (p == null) { 140         return 0; 141     } else { 142         return k; 143     } 144 } 145  146 /*插入数据元素 listinsert(l, i, e)*/ 147 bool listinsert(linklist* &l, int i, elemtype e) { 148     linklist *p = l; 149  150     int k = 0; 151     while(k < i - 1 && p != null) {//找到前驱节点 152         p = p -> next; 153         k++; 154     } 155  156     if (p == null) { 157         return false; 158     } else { 159         linklist *s; 160         s = (linklist *)malloc(sizeof(linklist)); 161         s -> data = e; 162         s -> next = p -> next; 163         p -> next = s; 164         return true; 165     } 166 } 167  168 /*删除数据元素 listdelete(l, i, e)*/ 169 bool listdelete_wq(linklist* &l, int i, elemtype &e) { 170     linklist *pre = l;//保存第 i 个指针的前驱 171     linklist *p = l -> next;//保存第 i 个指针的位置 172  173     int k = 1; 174     while(k < i && p != null) { 175         pre = pre -> next; 176         p = p -> next; 177         k++; 178     } 179  180     if (p == null) { 181         return false; 182     } else { 183         e = p ->data; 184         pre -> next = p -> next; 185         free(p); 186         return true; 187     } 188 } 189  190 bool listdelete(linklist* &l, int i, elemtype &e) { 191     linklist *pre = l;//保存第 i 个指针的前驱 192  193     int k = 0; 194     while(k < i - 1 && pre != null) { 195         pre = pre -> next; 196         k++; 197     } 198  199     if (pre == null) { 200         return false; 201     } else { 202         linklist *p; 203         p = pre -> next; 204         if (p == null) { 205             return false; 206         } 207         e = p -> data; 208         pre -> next = p -> next; 209         free(p); 210         return true; 211     } 212 } 213  214 int main(int argc, char const *argv[]) { 215     int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 216     linklist *l; 217     initlist(l); 218     //createlistr(l, a, 9); 219     createlistf(l, a, 9); 220     displist(l); 221     printf("length = %dn", listlength(l)); 222     elemtype e; 223     getelem(l, 4, e); 224     printf("fourth number = %dn", e); 225     printf("%d is located at %dn", e, locateelem_wq(l, 6)); 226     listinsert(l, 2, 10); 227     displist(l); 228     listdelete_wq(l, 2, e); 229     displist(l); 230     return 0; 231 }