title: 第二章
grammar_cjkRuby: true
[TOC]
一.线性表的概念及运算方法
线性表的逻辑结构
线性表是n个数据元素的有限序列线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
- 根据他们之间的关系，可以排成一个线性序列，记作：(a1,a2,...,an)
- 这里的a属于同一数据对象，具有相同的数据类型。
- 线性表的特点
- 同一性：线性表由同一数据类型组成，每一个a[i]必须属于同一数据对象
- 有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数
- 有序性：线性表中相邻的两个元素之间存在着序偶关系<a[i],a[i+1]>.
线性表的运算
线性表可以进行增删改查，也可以加长或者剪短线性表的长度
1. InitList(L),线性表初始化，创造一个新的线性表
2. ListLength(L),求线性表的长度，返回线性表L中数据元素的个数
3. GetElem(L,i,x),用x返回线性表中第i数据元素的值
4. LocationElem(L,x),按值查找，确定数据元素x在表中的位置
5. ListInsert(L,i,x),插入操作，在线性表L中第i个位置之前插入一个新元素x，L的长度加一。
6. LIstDelete(L,i),删除操作，删除线性表L中的第i个元素，线性表的长度减一。
7. ListEmpty(L),判断线性表是否为空，是空则返回true，不是空则返回false。
8. ClearList(L),将已知的线性表置成空表。
9. DestoryList(L),销毁线性表。
二.线性表的顺序储存
1. 顺序表
- 顺序储存：顺序储存是指在内存中用一块连续的储存空间按顺序储存线性表的各个元素。采取顺序储存结构的储存表叫做顺序表。
- 线性表的这种机内表示称为线性表的顺序储存结构或顺序映像
- **只要知道了顺序表的起始位置，线性表中任意数据元素都可以随机存取，顺序表是一种随机存取结构
- 线性表的顺序储存结构可以描述如下：
# define MAXSIZE<线性表可能达到的最大长度>
typedef int ElemType;
typedef struct{
ElemType elem[MAXSIZE];
int length; //线性表长度
}seqList;
定义一个顺序表：
seqList *L;
顺序表的长度为L->length,数据元素是L->elem[1]~L->elem[length],因C语言中数组的下标是从0开始的，为了一线性表中的数据元素的位序保持一致，可不使用数组下标为0的单元，下标的取值范围是1<=i<=MAXSIZE-1
2. 顺序表的基本运算
(1). 顺序表的初始化
创造一个空表，将表长length设为0，表示表中没有数据。
调用方法为：
Init_SeqList(&L);
(2).顺序表的插入
- 操作步骤如下：
- 将a(n)~a(i)按从后向前的顺序向下移动，为新元素让出位置。
- 将x放在空出的第i个位置。
- 修改表长。
(3). 顺序表的删除
- 操作步骤
- 将a(i+1)~a(n)依次向上移动；
- 将length值减1.
(4). 在顺序表中按值查找
线性表中的按值查找是指在线性表中查找第一个与给定值x相等的数据元素。
- 算法思想
- 从第一个元素a(1)起依次和x比较，直到找到一个与x的值相等的数据元素，返回它在序列表中的序号；若查遍整个线性表都没有找到与x相等的元素，则返回FALSE。
顺序表的特点
** 线性表顺序储存的特点是用物理位置上的相邻来表示数据元素之间逻辑相邻的关系，储存密度高，且能随机的存储数据；但在进行插入，删除时会移动大量数据元素，运行效率低。而且顺序表需要事先分配储存空间若N的值变化较大时，则存储规模难以确定，估计过大会导致存储空间的浪费。**
三. 线性表的链式结构
1.单链表
单链表的定义
- 每一个单链表都是由一个个节点组成，节点包括两部分，储存数据的数据域和储存当前节点的下一个节点的地址信息。
- 节点定义如下：
typedef struct node
{
ElemType date; //数据域
struct node *next; //指针域
} LNode,*LinkList;
头结点，头指针
- 在单链表的第一个节点之前会附加一个节点，叫做头节点，头结点的数据域可以储存标题，表长等信息，头结点的指针域储存第一个节点的首地址，头结点由头指针指向。
由于最后一个节点没有后继节点，所以他的指针域为空（NULL）用^表示。 - 头指针变量的定义：LinkList H;
- 算法中用到的指向某节点的指针变量的声明：LNode *p;
- 语句p=(LinkList)malloc(sizeof(LNode));表示申请一个LNode类型的储存空间的操作，并且将值赋给变量P
2.单链表的基本运算
建立单链表
单链表的建立有两种方法，头插法和尾插法
头插法
- 首先申请一个头结点，并且将头结点的指针域设为空
- 每读入一个数据都申请一个节点，都插入链表的头节点之后。
- 因为是在链表的头部插入节点，所以数据读入顺序和线性表中的逻辑顺序正好相反。
建立单链表的例子
#include<stdio.h>
#include<stdlib.h>
typedef struct student //定义一个结构体-》抽象数据类型
{
int name;
struct student *next;
}list,*Llist; //list指结构体名 ， *Llist指这个结构体的指针，相当于强制类型转换中的 （list *）
//创建一个节点（结构体），用来保存数据
Llist CreatList() //创建一个单链表，名字叫做 CreatList
{
int num=1;
Llist head = (list *)malloc(sizeof(list)); //定义一个头指针，并且给头指针分配储存空间
head->next=NULL; //让头指针指向为空
list *s; //定义数据类型为list的指针*s用来做节点
int x;
scanf("%d",&x); //输入需要保存的数据
while(x!=-1) //
{
s = (Llist)malloc(sizeof(list)); //为新建立的节点分配空间
s->name = x;
s->next = head->next; //新节点的指针域指向空
head->next=s; //让头结点指向新节点
printf("输出次数%d",num);
num++;
scanf("%d",&x);
}
return head; //所有的链表最后都要返回头指针
}
int main()
{
printf("shuru");
CreatList(); //调用链表
}
尾插法
在单链表的尾部插入节点建立单链表
- 由于每次是将新节点插入到链表的尾部，所以增加一个尾指针r来始终指向链表中的尾节点以便能够将结点插入到链表的尾部。
- 首先申请一个头结点，并将头结点指针域设空，头指针h和尾指针r都指向头结点
- 然后按线性表中元素的顺序依次读入数据元素，如果不是结束标志，则申请结点
- 将新的结点插入r所指结点的后面，并使r指向新结点。
尾插法建立链表代码实现
2. 求表长
算法思路：设一个指针p和计数器j，初始化使p指向结点H,j=0.若p所指的结点还有后继结点,p向后移动，计数器加1，重复上述过程，直到p->next=NULL为止。
3. 查找操作
- 按序号查找Get_Linklist(H,k)
思路：从链表的第一个结点起判断当前结点是否是第k个，如果是，则返回该节点的指针，否则继续查找下一个直到结束为止。没有第k个结点时返回空。
- 按值x查找（及查找x节点的位置）
思路：从链表的第一个结点起判断当前结点的值是否等于x，如果是，则返回该节点的指针，否则继续查找下一个直到结束为止。没有第k个结点时返回空。
4. 插入操作
设p指向单链表中的某结点，s指向待插入的新结点，将*s插入到 *p的后面，插入过程如下：
(1): s->next=p->next;
(2): p->next=s;
q=H;
while(q->next!=p)
q=q->next; //找*p的直接前驱
s->next=q->next;
q->next=s; //插入
- 将新结点*s插入到i个结点的位置上，即插入到a(i-1)与a(i)之间。算法思路如下：
- 查找第i-1个结点，若存在，继续2,否则结束。
- 创建新结点
- 将新节点插入，结束。
5. 删除操作
设p指向单链表中要删除的结点，首先找到*p的前驱结点 *q,然后完成删除操作，操作过程如下：
- q->next=p->next;
- free(p);
- 删除链表中的第i个结点。算法思路如下
- 查找第i-1个结点，若存在，则继续2，若不存在则结束；
- 若存在第i个结点，则继续3，否则，结束；
- 删除第i个结点否则结束
3. 循环链表
- 在单链表的基础上，将其最后一个结点的指针域指向该链表头结点，使得链表头尾结点相连，就构成了单循环链表。
- 特点：
- 循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。①循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
- 在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
4. 双向链表
- 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
- 结点的定义：
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
- 双向链表的定义：
带头结点的双向循环链表的基本操作
void InitList(DuLinkList L)
{ /* 产生空的双向循环链表L */
L=(DuLinkList)malloc(sizeof(DuLNode));
if(L)
L->next=L->prior=L;
else
exit(OVERFLOW);
}
静态链表
- 用数组描述的链表，即称为静态链表。在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标CUR。
- 静态链表结点的定义：
#define MAXSIZE 100;
typedef struct
{
ElemType data;
int cur;
}component,SLinkList[MAXSIZE];
- 静态链表的优点：
这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。
- 静态链表和动态链表的区别：
有些高级语言中没有“指针”数据类型，只能用数组来模拟线性链表的结构，
数组元素中的指针“域”存放的不是元素在内存中的真实地址，而是在数组中的位置。这样的链表
称为静态链表。而通过定义一个较大的结构体数组来作为备用结点空间(即存储池)，
每个结点应至少含有两个域：data域和cursor域。
四. 顺序表和链表的比较
- 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。
- 顺序表的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充
- 由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。
- 1 顺序表和链表的时间性能比较
所谓时间性能是指实现基于这种存储结构的基本运算（即算法）的时间复杂度。
像取出线性表中第 i 个元素这样的按位置随机访问的操作，使用顺序表更快一些；取前趋和后继结点的操作在顺序表中可以很容易调整当前的位置向前或向后，因此这两种操作的时间为 Ｏ (1) ；相比之下，单链表不能直接访问上述的元素，按位置访问只能从表头开始，直到找到那个特定的位置，所需要的平均时间为 Ｏ ( n ) 。
给出指向链表中某个合适位置的指针后，插入和删除操作所需的时间仅为 Ｏ （ 1 ），而顺序表进行插入和删除操作需移动近乎表长一半的元素，需要的平均时间为 Ｏ ( n ) 。这在线性表中元素个数较多时，特别是当每个元素占用的空间较多时，移动元素的时间开销很大。对于许多应用，插入和删除是最主要的操作，因此它们的时间效率是举足轻重的，仅就这个原因而言，链表经常比顺序表更好。
作为一般规律，若线性表需频繁查找却很少进行插入和删除操作，或其操作和“数据元素在线性表中的位置”密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作时，则宜采用链表做存储结构。
- 2 顺序表和链表的空间性能比较
所谓空间性能是指这种存储结构所占用的存储空间的大小。
首先定义结点的 存储密度 。
#include<stdio.h>
#include<stdlib.h>
struct Lnode/*定义链表*/
{
int number;
int password;
struct Lnode *next;
}Lnode,*p,*q,*head;
int main(void)
{
int n;/*n个人*/
int i;
int m;/*初始报数上限值*/
int j;
printf("pleaseenterthenumberofpeoplen:");/*输入测试人的数量*/
scanf("%d",&n);
loop:if(n<=0||n>30)/*检验n是否满足要求，如不满足重新输入n值*/
{ printf("\nniserorr!\n\n");
printf("pleaseenterthenumberofpeopleagainn:");
scanf("%d",&n);
goto loop;
}
for(i=1;i<=n;i++)/*建立单链表*/
{
if(i==1)
{
head=p=(struct Lnode*)malloc(sizeof(struct Lnode));
}
else
{
q=(struct Lnode*)malloc(sizeof(struct Lnode));
p->next=q;
p=q;
}
printf("pleaseenterthe%dpeople'spassword:",i);/*输入每个人所持有的密码值*/
scanf("%d",&(p->password));
p->number=i;
}
p->next=head;/*形成循环链表*/
p=head;
printf("pleaseenterthenumberm:");
scanf("%d",&m);
printf("Thepasswordis:\n");
for(j=1;j<=n;j++)/*输出各人的编号*/
{
for(i=1;i<m;i++,p=p->next);
m=p->password;
printf("%d",p->number);
p->number=p->next->number;/*删除报m的节点*/
p->password=p->next->password;
q=p->next;
p->next=p->next->next;
free(q);
}
printf("\n\n");
system("pause");/*等待按任意键退出*/
}
/*
一元多多项式的加法
1.先创建链表，存储多项式
2.输出多项式
3.两个多项式相加
4.输出多项式
*/
# include <stdio.h>
# include <malloc.h>
typedef struct dxs //多项式节点
{
float coe; //系数
int exp; //指数
struct dxs * pNext; //指针域
}DXS, * PDXS;
PDXS creat_dxs(); //创建多项式
void traverse(PDXS pHead); //遍历多项式链表
PDXS add(PDXS Da, PDXS Db); //多项式求和
int main(void)
{
//用链表结构，创建两个多项式
PDXS Da = creat_dxs();
traverse(Da);
PDXS Db = creat_dxs();
traverse(Db);
//求两个多项式的加法
PDXS Dj = add(Da, Db);
traverse(Dj);
return 0;
}
PDXS creat_dxs()
{
PDXS pHead = (PDXS)malloc(sizeof(DXS)); //创建头结点
pHead->pNext = NULL; //尾指针
PDXS pTail = pHead;
PDXS pNew = NULL;
int len;
float c;
int e;
int i;
printf("输入多项式的项数：len = ");
scanf("%d", &len);
for(i = 0; i < len; i++)
{
printf("分别输入第%d项的系数c、指数e:", i+1);
scanf("%f%d", &c, &e);
pNew = (PDXS)malloc(sizeof(DXS));
//多项式项，系数、指数
pNew->coe = c;
pNew->exp = e;
pNew->pNext = NULL;
pTail->pNext = pNew;
pTail = pNew;
}
return pHead;
}
//遍历链表
void traverse(PDXS pHead)
{
PDXS p = pHead->pNext; //首节点
while(p != NULL)
{
printf("(%.2f %d), ", p->coe, p->exp);
p = p->pNext;
}
printf("\n");
}
//多项式相加
PDXS add(PDXS Da, PDXS Db)
{
PDXS Dj = (PDXS)malloc(sizeof(DXS)); //和的头结点
Dj->pNext = NULL;
PDXS pTail = Dj; //和的尾节点
PDXS Dah = Da->pNext; //指向多项式的首节点
PDXS Dbh = Db->pNext;
//循环遍历多项式A，B
while(Dah && Dbh)
{
//比较当前两节点的指数
//当前 A项节点指数 < B项节点指数
if(Dah->exp < Dbh->exp)
{
pTail->pNext = Dah; //将此A项加入和链表中
pTail = Dah;
Dah = Dah->pNext; //A多项式向后遍历
}
//当前 A项节点指数 < B项节点指数
else if(Dah->exp > Dbh->exp)
{
pTail->pNext = Dbh; //将此B项加入和链表中
pTail = Dbh;
Dbh = Dbh->pNext; // //B多项式向后遍历
}
//如果两节点的指数相等
else
{
//当前指数的系数和不为0
//A项中保存系数和，把此A项加入和链表中
if(0 != (Dah->coe + Dbh->coe))
{
Dah->coe = Dah->coe + Dbh->coe;
pTail->pNext = Dah;
pTail = Dah;
}
//A,B都向后遍历
Dah = Dah->pNext;
Dbh = Dbh->pNext;
}
}
//插入剩余段
if(Dah != NULL)
{
pTail->pNext = Dah;
}
if(Dbh != NULL)
{
pTail->pNext = Dbh;
}
return Dj;
}
