佛科院计算机软件技术基础——线性表

一、基础知识了解：

1. 结构体的理解：

我们知道整型是由1位符号位和15位数值位组成，而就可以把结构体理解为我们定义的数据类型，如：

typedef struct
{int data[2];        //存储顺序表中的元素int len;                        //顺序表的表长
}SeqList;                             //顺序表类型

在这个结构体中我们定义前2*16位存放顺序表中的数据，最后1*16位存放表长

对于：

SeqList List;

这个就是类似于整型的一个结构体类型的变量，我们可以通过（List.len/List.data[i]）调用结构体变量中的元素。

对于：

SeqList *L;//等同于int *L;,只不过可指向的数据类型不同

不过跟int *L;相同的，定义只是一个空指针，需要通过申请一段内存空间才能使用：

L=(SeqList*)malloc(sizeof(SeqList));

2. 结构体变量的地址：

结构体变量的地址为首个成员的地址

3. 指针的理解:

指针是一种通过指向地址来操纵数据的方式

如：

typedef struct
{//MAXSIZE是根据实际问题所定义的一个足够大的整数//datatype为顺序表中元素的类型，在具体实现中可为int、float、char类型或其他结构类型datatype data[MAXSIZE];        //存储顺序表中的元素int len;                        //顺序表的表长
}SeqList;                             //顺序表类型//构造一个空表
SeqList *Init_SeqList()
{SeqList *L;//建立一个SeqList类型的空指针L=(SeqList*)malloc(sizeof(SeqList));//申请空间，并让L指向该空间的地址L->len=0; //顺序表的表长为0return L;
}

4. 对SeqList **L的理解：

对于：

typedef struct node
{datatype data;            //data为结点的数据信息struct node *next;      //与SeqList *L;类似，存放了另一个LNode结构体变量的首地址
}LNode;                                  

我们可以重点看struct node *next; ，如果我们要操作next地址对应结构体的数据data，我们就要用到SeqList **L

如：

一、顺序表

1. 顺序表定义：

typedef struct
{//datatype为表中元素类型（int,float等）//元素存放在data数组中//MAXSIZE是根据实际问题所定义的一个足够大的整数datatype data[MAXSISE];int len;//表长
}SeqList;

2. 指向顺序表的指针变量

SeqList list,*L;
//list是结构体变量，它内部含有一个可存储顺序表的data数组
//L是指向List这类结构体变量的指针变量

其中：

（1）List.data[i]或L->data[i]均表示顺序表中第i个元素的值

（2）List.len或L->len均表示顺序表的表长

（3）“L=(SeqList*)malloc(sizeof(SeqList));”表示生成一个顺序表存储空间

3. 顺序表的初始化

typdefine struct 
{datatype data[MAXSIZE];int len;
}Seqlist;
Seqlist *seqlist_Init()
{Seqlist *l;l = (Seqlist*)malloc(sizeof(Seqlist));l->len = 0;return l;
}

4. 建立顺序表：（没搞懂）

（1）头部插入

先读取需要输入数据个数，再进行读取外部数据操作，最后将数据按顺序存放到顺序表中的数组

void CreatList(SeqList **L)
{int i, n;printf("Input length of List: ");scanf("%d", &n);printf("Input elements of List: \n");for(i=1;i<=n;i++)scanf("%d", &(*L)->data[i]);(*L)->len=n;
}

（2）尾部插入

LNode *CreateLinkList()
{LNode *head, *p, *q; char x;head=(LNode*)malloc(sizeof(LNode));       //生成头结点head->next=NULL;p=head; q=p;                                    //指针q始终指向链尾结点printf("Input any char string: \n");scanf("%c", &x);while(x!='\n')                                  //生成链表的其他结点{p=(LNode*)malloc(sizeof(LNode));p->data=x;p->next=NULL;q->next=p;                                    //在链尾插入q=p;scanf("%c", &x);}return head;                                   //返回单链表表头指针
}

5. 插入运算：

先判断表是否满了和插入位置是否合理，再将i到len个从后面到前面逐个向后移，最后再插入到第i个位置

void Insert_SeqList(SeqList *L, int i, datatype x)
{int j;if(L->len==MAXSIZE-1)                   //表满printf("The List is full!\n");elseif(i<1|| i>L->len+1)                //插入位置非法printf("The position is invalid !\n");else{for(j=L->len;j>=i;j--)          //将an～ai顺序后移一个元素位置L->data[j+1]=L->data[j];L->data[i]=x;                   //插入x到第i个位置L->len++;                          //表长增1}
}}

6. 删除运算：

void Del_LinkList(LNode *head , int i)
{                     //删除单链表head上的第i个数据结点LNode *p, *q;p=Get_LinkList(head, i-1);               //查找第i-1个结点if(p==NULL)printf("第i-1个结点不存在!\n "); //待删结点的前一个结点不存在，无待删结点elseif(p->next==NULL)printf("第i个结点不存在!\n");        //待删结点不存在else{q=p->next;                //q指向第i个结点p->next=q->next;            //从链表中删除第i个结点free(q);                //系统回收第i个结点的存储空间}
}

7. 查找：

给值查找存储位置：以该一位元素是否为x和该位是否在在顺序表中为判断条件，最后如果跳出时的元素为x则返回i，不是则返回0

int Location_SeqList(SeqList *L, datatype x)
{int i=1;                                  //从第一个元素开始查找while(i<L->len&&L->data[i]!=x)//顺序表未查完且当前元素不是要找的元素i++;if(L->data[i]==x)return i;                                //找到则返回其位置值elsereturn 0;                                              //未找到则返回0值
}

二、单链表

1. 单链表结点定义：

只需要定义一个存放数据和后一个节点地址的结构体就行

typedef struct node
{datatype data;            //data为结点的数据信息struct node *next;      //next为指向后继结点的指针
}LNode;                                  //单链表结点类型

2. 建立单链表：

首先建立一个任意的头节点，读取外部输入数据，

void CreateLinkList(LNode **head)
{                       //将主调函数中指向待生成单链表的指针地址（如&p）传给**headchar x;LNode *p;*head=(LNode *)malloc(sizeof(LNode)); //在主调函数空间生成链表头结点(*head)->next=NULL;        //*head为链表头指针printf("Input any char string: \n");scanf("%c", &x);      //结点的数据域为char型，读入结点数据while(x!='\n')             //生成链表的其他结点{p=(LNode *)malloc(sizeof(LNode));     //申请一个结点空间p->data=x;p->next=(*head)->next;       //将头结点的next值赋给新结点*p的next(*head)->next=p;    //头结点的next指针指向新结点*p实现在表头插入scanf("%c", &x);            //继续生成下一个新结点}

（1）为什么使用LNode **head？（未解决）

由于我们要与主函数联系起来，必须确定头节点的

3. 查找：

（1）按序号：

根据指针域一直寻址到第i个结点，以循环次数与最后一个节点为结束标志

LNode *Get_LinkList(LNode *head, int i)
{                                 //在单链表head中查找第i个结点LNode *p=head;              //由第一个结点开始查找int j=0;while(p!=NULL&&j<i)         //当未查到链尾且j小于i时继续查找{p=p->next;j++;}return p;           //找到则返回指向i结点的指针值，找不到则p返回空值
}

（2）按值查找：

根据指针域一直寻址，以找到目标值和最后一个数为结束标志

LNode *Locate_LinkList(LNode *head, char x)
{                                //在单链表中查找结点值为x的结点LNode *p=head->next;     //由第一个数据结点开始查找while(p!=NULL&&p->data!=x) //当未查到链尾且当前结点不等于x时继续查找p=p->next;return p; //找到则返回指向值为x的结点的指针值，找不到则p返回空值
}

4. 求表长：

从第一个结点寻址到最后一个结点，并做计数

int Length_LinkList(LNode *head)
{LNode *p=head;                //p指向单链表头结点int i=0;                         //i为结点计数器while(p->next!=NULL){p=p->next;i++;}return i;                       //返回表长值i
}

5. 插入：

利用查找函数获得第i-1个结点的地址，如果该结点地址为空（即最后一个结点），说明插入操作非法；如果不为空，创建一个新节点数据域存放插入数据，指针域域存放下一个结点的地址，上一个结点的指针域放新节点的地址

void Insert_LinkList(LNode *head, int i, char x)
{                                               //在单链表head的第i个位置上插入值为x的元素LNode *p, *q;p=Get_LinkList(head, i-1);            //查找第i-1个结点*/if(p==NULL) printf("Error ! \n");                 //第i-1个位置不存在而无法插入else{q=(LNode *)malloc(sizeof(LNode));    //申请结点空间q->data=x;q->next=p->next;                      //完成插入操作①p->next=q;                             //完成插入操作②}
}

6. 删除：

首先像插入操作一样判断删除操作是否非法，如果合法，则让第i-1个结点的地址域直接存放第i+1个结点的地址，同时把第i个结点的空间释放

算法如下：
void Del_LinkList(LNode *head , int i)
{                     //删除单链表head上的第i个数据结点LNode *p, *q;p=Get_LinkList(head, i-1);               //查找第i-1个结点if(p==NULL)printf("第i-1个结点不存在!\n "); //待删结点的前一个结点不存在，无待删结点elseif(p->next==NULL)printf("第i个结点不存在!\n");        //待删结点不存在else{q=p->next;                //q指向第i个结点p->next=q->next;            //从链表中删除第i个结点free(q);                //系统回收第i个结点的存储空间}
}

三、循环链表

1. 查找循环链表中某个数：

与单链表类似，只不过最后的一个查找的地址不是NULL而是头节点

LNode *Locate_CycLink(LNode *head, datatype x)
{LNode *p=head->next;       //由第一个数据结点开始查while(p!=head&&p->data!=x)//未查完循环链表且当前结点不等于x时继续查找p=p->next;if(p!=head)                       //head   代表结束点return p;              //找到值等于x的结点*p，返回其指针值pelsereturn NULL; //当p又查到头结点时则无等于x值的结点，故返回NULL值
}

四、单链表应用

例1：

通过两个指针将

void Convert(LNode *H)
{LNode *p, *q;p=H->next;               //p指向剩余结点链表的第一个数据结点H->next=NULL;               //新链表H初始为空while(p!=NULL){q=p;                   //从剩余结点链表中取出第一个结点p=p->next;             //p继续指向剩余结点链表新的第一个数据结点q->next=H->next;     //将取出的结点*q插入新链表H的链首H->next=q;}
}

例2：

首先把A的头节点赋给C，释放B的头节点，再将A、B中较小的用头插法赋给C，再该链表推进到下一个结点，循环该操作直到A,B中任意一方到最后一个结点，最后将剩余元素用头插法赋给C

 void Merge(LNode *A, LNode *B, LNode **C)
{                           //将增序链表A、B合并成降序链表*CLNode *p, *q, *s;p=A->next;              //p始终指向链表A的第一个未比较的数据结点q=B->next;               //q始终指向链表B的第一个未比较的数据结点*C=A;                     //生成链表的*C的头结点(*C)->next=NULL;free(B);                 //回收链表B的头结点空间while(p!=NULL&&q!=NULL){   //将A、B两链表中当前比较结点中值小者赋给*sif(p->data<q->data){s=p;   p=p->next;}else{s=q； q=q->next;}s->next=(*C)->next; //用头插法将结点*s插到链表*C的头结点之后(*C)->next=s;}if(p==NULL)    //如果指向链表A的指针*p为空，则使*p指向链表Bp=q;while(p!=NULL){//将*p所指链表中的剩余结点依次摘下插入链表*C的链首s=p；p=p->next;s->next=(*C)->next;   (*C)->next=s;}

例3：

首先建立一个单链表，再将最后一个地址域赋上头节点地址形成循环列表，

void Josephus(int n, int m, int k)
{LNode *p, *q;int i;p=(LNode*)malloc(sizeof(LNode));q=p;for(i=1;i<n;i++)     //从编号k开始建立一个单链表{q->data=k;k=k%n+1;q->next=(LNode*)malloc(sizeof(LNode));q=q->next;}q->data=k; q->next=p;              //链接成循环单链表，此时p指向编号为k的结点while(p->next!=p)       //当循环单链表中的结点个数不为1时{for(i=1;i<m;i++){q=p;  p=p->next;}                          //p指向报数为m的结点，q指向报数为m-1的结点q->next=p->next;              //删除报数为m的结点printf("%4d", p->data);       //输出出圈人的编号free(p);                      //释放被删结点的空间p=q->next;                    //p指向新的开始报数结点}printf("%4d", p->data);         //输出最后出圈人的编号
}