线性表操作

问题描述：

两个递增有序的线性表A，B表示两个集合，要求另给一空间构成线性表C，其元素为A和B中元素的交集，且C中的元素是递增有序，试对顺序表编写求C的算法。

问题分析：

有了上个题目的基础，这个题的解法应该容易想到些，两个线性表本身就是递增有序的，遍历的时候，比较两个线性表的元素，当相同时，把它加到C表中，这样就把C表构造成功了。

关键对于我来说，怎样为表分配一空间，不是很清楚，还有这道题和上个题目的不同之处在于，C表的空间分配好后是往后面添加元素，记得前一个题是在它的前面加元素。

先看下线性表的动态分配顺序存储结构：

#define LIST_INIT_SIZE 100 //线性表存储空间的起始分配量

#define LISTINCREMENT 10//线性表存储空间的分配增量

typedef struct{

ElemType *elem;//存储空间基址

int length;//当前长度

int listsize;//当前分配的存储容量（以sizeof（ElemType）为单位）

}SqList;

再看下怎样为新的链表C添加数据：

SqList &C;

//构造一个空的线性表C

C.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!C.elem) exit(OVERFLOW);//存储分配失败

C.length=0;//空表的长度为0

C.listsize=LIST_INIT_SIZE;//初始存储容量

char *p;

Status ListInsert_Sq(SqList &C,ElemType A.elem[i])

{

if(C.length>=C.listsize)

{

newbase=(ElemType *)realloc(C.elem,(C.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase) exit(OVERFLOW);//存储分配失败

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;增加存储容量

}

p=&(C.elem[C.length]);//p为插入的位置

*p=A.elem[i];//将元素插入

C.Length++;//表的长度加1

return OK;

}

最后是将两个线性表A,B的交集抽出来

Status ListCross_Sq(SqList &A,SqList &B,SqList &C)

{

int i=0,j=0;

while(i<A.length&&j<B.length)

{

if(A.elem[i]<B.elem[j])

i++;

else

if(A.elem[i]>B.elem[j])//体会这两个if嵌套的巧妙之处

j++;

else

{

ListInsert_Sq(C,A.elem[i]);

i++;

}

return OK;

}

　解决的算法，差不多就这些了。

2013-05-27 这一天对以前做的作业进行了修改，发现自己以前做的欠缺思考了，是应付？没有用心吗？现在改了，希望自己能越做越好！

单链表实现的代码：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 typedef struct LNode{
  4 int data;
  5 struct LNode *next;
  6 }LNode,*LinkList;//结构体类型，结构体名
  7 LinkList ListCross_L(LinkList A,LinkList B,LinkList C)
  8 {
  9     LNode *pa,*pb,*qa,*qb,*pt;
 10     pa=A;
 11     pb=B;
 12     qa=pa;
 13     qb=pb;//前驱指针
 14     pa=pa->next;
 15     pb=pb->next;
 16     C=A;
 17     while(pa&&pb)
 18     {
 19         if(pa->data>pb->data)
 20         {
 21             pt=pb;
 22             pb=pb->next;
 23             qb->next=pb;
 24             free(pt);
 25         }
 26         else
 27         {
 28             if(pa->data<pb->data)
 29             {
 30                 pt=pa;
 31                 pa=pa->next;
 32                 qa->next=pa;
 33                 free(pt);
 34             }
 35             else//交集
 36             {
 37                 qa=pa;
 38                 pa=pa->next;
 39             }
 40         }
 41     }
 42     while(pa)
 43     {
 44         pt=pa;
 45         pa=pa->next;
 46         qa->next=pa;
 47         free(pt);
 48     }
 49     while(pb)
 50     {
 51         pt=pb;
 52         pb=pb->next;
 53         free(pt);
 54     }
 55     pb=B;
 56     free(pb);
 57    return C;
 58     
 59 }
 60 struct LNode* CreateLinkList(LinkList head)
 61 {
 62     int t;
 63     LNode *p;
 64     head=(LNode *)malloc(sizeof(LNode));
 65     head->next=NULL;
 66     while(scanf("%d",&t)&&t!=0)//以0作为结束判断标志
 67     {
 68         p=head;//在建好的单链表中，以p为扫描指针，从头开始查找有无数据与t相同的
 69         while((p->next)&&(t!=p->next->data))
 70             p=p->next;
 71         if(p->next)
 72             printf("已经存在此数：%d",t);
 73         else
 74         {
 75           p->next=(LNode *)malloc(sizeof(LNode));
 76           //在单链表表尾申请一个新结点
 77           p=p->next;
 78           p->data=t;//将t的值复制到*p结点的数据域中。
 79           p->next=NULL;
 80         }
 81     }
 82 /*    LNode *p1;
 83     p1=head->next;
 84     while(p1)
 85     {
 86       printf("%d",p1->data);
 87       p1=p1->next;
 88     }
 89 */
 90     return head;
 91 }
 92 int main()
 93 {
 94     LinkList A,B,C;
 95     printf("为A链表赋值：\n");
 96     A=CreateLinkList(A);
 97     printf("为B链表赋值：\n");
 98     B=CreateLinkList(B);
 99     C=ListCross_L(A,B,C);
100     printf("链表C的值为：\n");
101     LNode *p1;
102     p1=C->next;
103     while(p1)
104     {
105       printf("%d",p1->data);
106       p1=p1->next;
107     }
108     
109 }

View Code

顺序表实现的代码：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define LIST_INIT_SIZE 100
 4 #define LISTINCREMENT 10
 5 typedef struct{
 6 int *elem;//存储空间基址
 7 int length;//当前长度
 8 int listsize;//当前分配存储容量
 9 }SqList;
10 void ListInsert_Sq(SqList &C,int c)
11 {
12   int *newbase,*p;
13   if(C.length>=C.listsize)
14   {
15       newbase=(int *)realloc(C.elem,(C.listsize+LISTINCREMENT)*sizeof(int));
16       if(!newbase)
17       exit(0);
18       C.elem=newbase;
19       C.listsize+=LISTINCREMENT;//增加存储容量
20   }
21   p=&(C.elem[C.length]);//p为插入位置
22   *p=c;//元素插入
23   C.length++;
24 }
25 void ListCross_Sq(SqList &A,SqList &B,SqList &C)
26 {
27     int i=0,j=0;
28     while(i<A.length&&j<B.length)
29     {
30         if(A.elem[i]<B.elem[j])
31             i++;
32         else
33             if(A.elem[i]>B.elem[j])
34                 j++;
35             else
36             {
37                 ListInsert_Sq(C,A.elem[i]);
38                 i++;
39             }
40     }
41 }
42 int main()
43 {
44    SqList A,B,C;
45    int A_len,B_len;
46    int *p,*q;
47    printf("输入A，B表的长度：");
48    scanf("%d%d",&A_len,&B_len);
49    A.length=A_len;
50    B.length=B_len;
51    A.elem=(int *)malloc(A_len*sizeof(int));
52    p=A.elem;
53    B.elem=(int *)malloc(B_len*sizeof(int));
54    q=B.elem;
55    printf("输入A表中各元素的值：");
56    for(int i=0;i<A_len;i++,p++)
57        scanf("%d",p);
58    printf("输入B表中各元素的值：");
59    for(int j=0;j<B_len;j++,q++)
60        scanf("%d",q);
61    C.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
62    C.length=0;
63    C.listsize=LIST_INIT_SIZE;
64    ListCross_Sq(A,B,C);
65    printf("输出C表元素的值：");
66    for(int k=0;k<C.length;k++)
67        printf("%d",C.elem[k]);
68 }

View Code