数据结构第二章总结
2.1线性表的逻辑结构
线性表是由n(n≥0)个数据元素组成的有限序列，当n=0是称为空表，非空的线性表记为(a1,a2,a3，an)。
线性表的基本运算有：
1)InitList(L),构造空表，即表的初始化;
2)ListLength(L),求表的结点个数，即表长;
3)GetNode(L,i),取表中第i个结点，要求1≤i≤ListLength(L);
4)LocateNode(L,x)查找L中值为x的结点并返回结点在L中的位置，有多个x则返回首个，没有则返回特殊值表示查找失败。
5)InsertList(L,x,i)在表的第i个位置插入值为x的新结点，要求1≤i≤ListLength(L)+1;
6)DeleteList(L,i)删除表的第i个位置的结点，要求1≤i≤ListLength(L);
2.2线性表的顺序存储结构
2.2.1顺序表
顺序表是把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。
结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C;1≤i≤n
顺序表的定义：
#define listsize 100
typedef int datatype;
typedef struct{
datatype data[listsize];
int length;
]seqlist;
2.2.2顺序表山的基本运算
1. 插入
void insertlist(seqlist *L,datatype x,int i)
{
int j;
if(i<1||i>L->length+1)
error(“position error”);
if(L->length>=listsize)
error(“overflow”);
for(j=L->length-1;j>=i-1;j--)
L->data[j+1]=L->data[j];
L->data[i-1]=x;
L->length++;
}
在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。
2.删除
void delete (seqlist *L,int i)
{
int j;
if(i<1||i>L->length)
error(“position error”);
for(j=i;j<=L->length-1;j++)
L->data[j-1]=L->data[j];
L->length--;
}
在顺序表上删除要移动表的(n+1)/2结点，算法的平均时间复杂度为O(n)。
2.3线性表的链式存储结构
用链接方式存储的线性表称链表。
2.3.1单链表
在结点中除了存储结点值还存储结点的后继结点的地址，data|next,data是数据域，next是指针域，只有一个链域的链表称单链表。
单链表结点的定义。
Typedef char datatype;
Typedef struct node{
Datatype data;
Struct node *next;
}listnode;
typedef listnode *linklist;
listnode *p;
linklist head;
结点的动态生成p=(listnode *)malloc(sizeof(listnode));结点的回收free(p);
1. 建立单链表。时间复杂度为O(n)。
1) 头插法建表。
Link createlistF(void)
{
char ch;
linklist head;
listnode *s;
head=NULL;
ch=getchar();
while(ch!='\n'){
s=(listnode *)malloc(sizeof(listnode));
s->data=ch;
s->next=head;
head=s;
ch=getchar();
}
return head;
}
2)尾插法建表。
Link createlistR(void)
{
char ch;
linklist head;
listnode *s, *r;
s=NULL;r=NULL;
while((ch=getchar())!='\n'){
s=(listnode *)malloc(sizeof(listnode));
s->data=ch;
if(head=NULL)
head=s;
else
r->next=s;
r=s;
}
if(r!=NNULL)
r->next=NULL;
return head;
}
在链表开始结点前附加一个头结点的优点是：1)链表第一个位置的操作无需特殊处理;2)将空表和非空表的处理统一。
3)带头结点的尾插法建表。
Linklist createlisR1(void)
{
char ch;
linklist head=(listnode *)malloc(sizeof(listnode));
listnode *s, *r;
r=head;
while((ch=getchar())!='\n'){
s=(listnode *)malloc(sizeof(listnode));
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
return head;
}
2. 查找运算。时间复杂度为O(n)。
1) 按序号查找。
Listnode * getnode(linklist head,int i)
{
int j;
listnode *p;
p=head;j=0;
while(p->next&&j<I){< p>
p=p->next;
j++;
}
if(i==j)
return p;
else
return NULL;
}
2) 按值查找。
Listnode * locatenode(linklist head ,datatype key)
{
listnode *p=head->next;
while(p&&p->data!=key)
p=p->next;
return p;
}
3. 插入运算。时间复杂度为O(n)。
Void insertlist(linklist head ,datatype x, int i)
{
listnode *p;
p=getnode(head,i-1);
if(p==NULL);
error(“position error”);
s=(listnode *)malloc(sizeof(listnode));
s->data=x;
s->next=p->next;
p->next=s;
}
4. 删除运算。时间复杂度为O(n)。
Void deletelist(linklist head ,int i)
{
listnode *p ,*r;
p=getnode(head ,i-1);
if(p==NULL||p->next==NULL)
error(“position error”);
r=p->next;
p->next=r->next;
free(r);
}
2.3.2循环链表。
循环链表是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。
单链表是将终端结点的指针域指向表头结点或开始结点。为使空表和非空表处理一致可设置一个头结点。
用头指针表示的单循环链表查找开始结点的时间是O(1),查找尾结点的时间是O(n);用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O(1)。
2.3.3双链表
在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。
双链表结点定义。
Typedef struct dlistnode{
Datatype data;
Struct dlistnode *prior,*next;
}dlistnode;
typedef dlistnode *dlinklist;
dlinklist head;
1) 双链表的前插操作。时间复杂度为O(1)。
Void dinsertbefore(dlistnode *p ,datatype x)
{
dlistnode *s=malloc(sizeof(dlistnode));
s->data=x;
s->prior=p->prior;
s->next=p;
p->prior->next=s;
p->prior=s;
}
2) 双链表的删除操作。时间复杂度为O(1)。
Void ddeletenode(dlistnode *p)
{
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
}
2.4顺序表和链表的比较。
1) 基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。
2) 基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。