实验二：数据结构之线性链表例程实践：集合的交运算，并运算，差运算

拼搏现实的明天。 2023-06-06 12:15 1阅读 0赞

1. 验证结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70][]

2. 完整源代码如下：

1 /*头文件*/
      2 #include <stdio.h>
      3 #include <string.h>
      4 #include <malloc.h>
      5 /*常量定义*/
      6 #define OK 0                        //成功执行
      7 #define Err_Memory -1               //内存分配错误 
      8 #define Err_InvalidParam -2         //输入参数无效
      9 #define Err_Overflow -3             //溢出错误
     10 #define Err_IllegalPos -4           //非法位置
     11 #define Err_NoResult -5             //无法返回结果或返回结果为空
     12 
     13 typedef char* ElemType;
     14 
     15 typedef struct node{
     16     ElemType data;
     17     struct node *next;
     18 }ListNode, *LinkList;
     19 
     20 typedef int Status;
     21 
     22 /*初始化线性表*/
     23 Status InitList(LinkList L)
     24 {
     25     if (!L)
     26       return Err_InvalidParam;
     27 
     28     L->next=NULL;
     29 
     30     return OK;
     31 }
     32 
     33 /*清空线性表*/
     34 Status ClearList(LinkList L)
     35 {
     36     ListNode *p, *q;
     37 
     38     if (!L)
     39       return Err_InvalidParam;
     40 
     41     p = L->next;
     42 
     43     while(p){
     44         q = p;
     45         p = p->next;
     46         free(q);
     47     }
     48 
     49     L->next = NULL;
     50 
     51     return OK;
     52 }
     53 
     54 /*测试线性表是否为空*/
     55 int EmptyList(LinkList L)
     56 {
     57     if (!L)
     58       return Err_InvalidParam;
     59 
     60     return (L->next == NULL);
     61 }
     62 
     63 /*求线性表的长度*/
     64 int LengthList(LinkList L)
     65 {
     66     int count = 0;
     67     ListNode *p;
     68     p = L->next;
     69     while(p){
     70         count++;
     71         p = p->next;
     72     }
     73     return count;
     74 }
     75 
     76 /*遍历线性表*/
     77 void TraverseList(LinkList L)
     78 {
     79     ListNode *p = L->next;
     80     while(p){
     81 //      printf("%d", p->data);
     82         printf("%s, ", p->data);
     83         p = p->next;
     84     }
     85 }
     86 
     87 /*向线性表中插入元素*/
     88 Status InsertList(LinkList L, int i, ElemType e)
     89 {
     90     ListNode *p, *s;
     91     int k = 1;
     92     if (!L)
     93         return Err_InvalidParam;
     94 
     95     p = L;
     96     while(k < i && p){
     97         k++;
     98         p=p->next;
     99     }
    100     if (k>i || !p)
    101         return Err_IllegalPos;
    102     s = (ListNode *)malloc(sizeof(ListNode));
    103     if(!s)
    104         return Err_Memory;
    105     s->data = e;
    106     s->next = p->next;
    107     p->next = s;
    108     return OK;
    109 }
    110 
    111 /*删除元素*/
    112 Status DeleteList(LinkList L, int i, ElemType *e)
    113 {
    114     ListNode *p, *q;
    115     int k = 1;
    116 
    117     if (!L)
    118         return Err_InvalidParam;
    119 
    120     p = L;
    121 
    122     while(k < i && p){
    123         k++;
    124         p=p->next;
    125     }
    126 
    127     if (k>i || !p)
    128         return Err_IllegalPos;
    129 
    130     q = p->next;
    131     p->next = q->next;
    132     *e = q->data;
    133     free(q);
    134 
    135     return OK;
    136 }
    137 
    138 /*定位元素*/
    139 int LocateList(ElemType e, LinkList L)
    140 {
    141     int i = 1;
    142     ListNode *p;
    143 
    144     if (!L)
    145         return Err_InvalidParam;
    146     p = L->next;
    147 
    148 //  while(p && p->data!=e){
    149     while(p && (strcmp(p->data, e) != 0)){
    150         i++;
    151         p = p->next;
    152     }
    153     if (!p)
    154       return 0;
    155 
    156     return i;
    157 }
    158 
    159 /*获取元素*/
    160 Status GetElem(LinkList L, int i, ElemType *e)
    161 {
    162     ListNode *p;
    163     int k = 1;
    164 
    165     if (!L)
    166         return Err_InvalidParam;
    167 
    168     p = L->next;    //注意与删除第i个元素的函数该行区别
    169 
    170     while(k < i && p){
    171         k++;
    172         p=p->next;
    173     }
    174 
    175     if (k>i || !p)
    176         return Err_IllegalPos;
    177 
    178     *e = p->data;
    179     return OK;
    180 }
    181 
    182 /*创建单链表*/
    183 Status CreateLinkList(LinkList L, int n)
    184 {
    185     ListNode *p, *s;
    186 
    187     int i = 1;
    188 
    189     if (!L)
    190         return Err_InvalidParam;
    191 
    192     p = L;
    193 
    194     for (i = 0; i<n; i++){
    195         s = (ListNode *)malloc(sizeof(ListNode));
    196         scanf("%d", &s->data);
    197         s->next = NULL;
    198         p->next = s;
    199         p = s;
    200     }
    201 
    202     return OK;
    203 }
    204 
    205 /*销毁链表*/
    206 Status DestroyLinkList(LinkList L)
    207 {
    208     ListNode *p;
    209 
    210     if (!L)
    211         return Err_InvalidParam;
    212 
    213     while(L){
    214         p = L;
    215         L = L->next;
    216         free(p);
    217     }
    218 
    219     return OK;
    220 }
    221 
    222 /*创建集合算法*/
    223 Status CreateCollection(LinkList C)
    224 {
    225     int count = 1;
    226     ListNode *s, *p;
    227     ElemType e;
    228 
    229     if (InitList(C) != OK)
    230       return Err_NoResult;
    231 
    232     p = C;
    233 
    234     while(1){
    235         s = (ListNode *)malloc(sizeof(ListNode));
    236         if(!s)
    237             return Err_Memory;
    238         e = (ElemType *)malloc(sizeof(char));
    239         if(!e)
    240             return Err_Memory;
    241         printf("请输入第%d个元素：", count++);
    242         gets(e);
    243         if(strcmp(e, "#") == 0)
    244             break;
    245         if(LocateList(e, C) == 0){
    246             if(InsertList(p, 1, e) != OK)
    247                 return Err_NoResult;
    248             p = p->next;
    249         }
    250     }
    251     return OK;
    252 }
    253 
    254 /*并运算算法*/
    255 Status Union(LinkList C, LinkList A, LinkList B)
    256 {
    257     ListNode *pa, *pb, *pc;
    258     ElemType e;
    259 
    260     if(!A || !B || !C)
    261       return Err_InvalidParam;
    262     pa = A->next;
    263     pb = B->next;
    264     pc = C;
    265 
    266     while(pa){
    267         e = (ElemType *)malloc((strlen(pa->data) + 1) * sizeof(char));
    268         strcpy(e, pa->data);
    269         if(InsertList(pc, 1, e) != OK)
    270             return Err_NoResult;
    271         pc = pc->next;
    272         pa = pa->next;
    273     }
    274 
    275     while(pb){
    276         if(LocateList(pb->data, A) == 0){
    277             e = (ElemType *)malloc((strlen(pb->data) + 1) * sizeof(char));
    278             strcpy(e, pb->data);
    279             if(InsertList(pc, 1, e) != OK)
    280                 return Err_NoResult;
    281             pc = pc->next;
    282         }
    283         pb = pb->next;
    284     }
    285 
    286     return OK;
    287 }
    288 
    289 /*交运算算法*/
    290 Status Intersect(LinkList C, LinkList A, LinkList B)
    291 {
    292     ListNode *pa, *pb, *pc;
    293     ElemType e;
    294 
    295     if(!A || !B || !C)
    296       return Err_InvalidParam;
    297     pa = A->next;
    298     pb = B->next;
    299     pc = C;
    300 
    301     while(pa){
    302         if(LocateList(pa->data, B) != 0){
    303             e = (ElemType *)malloc((strlen(pa->data) + 1) * sizeof(char));
    304             strcpy(e, pa->data);
    305             if(InsertList(pc, 1, e) != OK)
    306                 return Err_NoResult;
    307             pc = pc->next;
    308         }
    309         pa = pa->next;
    310     }
    311 
    312     return OK;
    313 }
    314 
    315 /*差运算*/
    316 Status Except(LinkList C, LinkList A, LinkList B)
    317 {
    318     ListNode *pa, *pb, *pc;
    319     ElemType e;
    320 
    321     if(!A || !B || !C)
    322       return Err_InvalidParam;
    323     pa = A->next;
    324     pb = B->next;
    325     pc = C;
    326 
    327     while(pa){
    328         if(LocateList(pa->data, B) == 0){
    329             e = (ElemType *)malloc((strlen(pa->data) + 1) * sizeof(char));
    330             strcpy(e, pa->data);
    331             if(InsertList(pc, 1, e) != OK)
    332                 return Err_NoResult;
    333             pc = pc->next;
    334         }
    335         pa = pa->next;
    336     }
    337 
    338     return OK;
    339 }
    340 
    341 /*main program*/
    342 void main()
    343 {
    344     LinkList A, B, C;
    345     ElemType s;
    346 
    347     A = (ListNode *)malloc(sizeof(ListNode));
    348     B = (ListNode *)malloc(sizeof(ListNode));
    349     C = (ListNode *)malloc(sizeof(ListNode));
    350     printf("请输入集合A的元素（输入#结束）：\n");
    351     if(CreateCollection(A) != OK){
    352         printf("集合A创建错误！\n");
    353         return;
    354     }
    355     printf("请输入集合B的元素（输入#结束）：\n");
    356     if(CreateCollection(B) != OK){
    357         printf("集合B创建错误！\n");
    358         return;
    359     }
    360     if(InitList(C) != OK){
    361         printf("集合C初始化错误！\n");
    362         return;
    363     }
    364     printf("\n集合A的元素为：\n");
    365     TraverseList(A);
    366     printf("\n集合B的元素为：\n");
    367     TraverseList(B);
    368     if(Union(C, A, B) != OK){
    369         printf("并运算失败！\n");
    370         return;
    371     }
    372     printf("\n集合A与B的并集为：\n");
    373     TraverseList(C);
    374     ClearList(C);
    375     if(Intersect(C, A, B) != OK){
    376         printf("交运算失败！\n");
    377         return;
    378     }
    379     printf("\n集合A与B的交集为：\n");
    380     TraverseList(C);
    381     ClearList(C);
    382     if(Except(C, A, B) != OK){
    383         printf("差运算失败！\n");
    384         return;
    385     }
    386     printf("\n集合A与B的差为：\n");
    387     TraverseList(C);
    388     printf("\n");
    389     ClearList(C);
    390     DestroyLinkList(A);
    391     DestroyLinkList(B);
    392     DestroyLinkList(C);
    393     return;
    394 }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70]: /images/20230601/f3d29e10727b4605bed5d52a1a1a984c.png