|
|
|
《数据结构》自学方法指导 |
|
|
来源： 发布时间：2006-5-29 16:56:48 点击： |
(1)插入运算：线性表的插入运算是指在标的第i(1≤i≤n+1)个位置上，插入一个新结点x，具体算法实现参考教材第15页的InsertList算法：
①判断插入位置是否正确？
当i<1或者i>L->length+1时，说明插入一个在线性表中不存在的位置
②判断表的存储空间是否已满？
当L->length=ListSize时，说明线性表已满
③将插入位点后面的元素后移一个位置
for(j=L->length-1;j>=i-1;j--)
L->data[j+1]=L->data[j];
④在插入点插入元素x,同时将表长加一：
L->data[i-1]=x;
L->length++;
注意点：
算法中结点后移的方向，必须从表中最后一个结点开始后移，直至将第i个结点后移为止；
(2)删除运算：
①判断删除位置是否正确？
i<1或者i>L-length,则删除位置错误
②删除位置以后的结点位置前移一个位置
for(j=i;j<=L->length-1;j++)
L->data[j-1]=L->data[j];
③表长减一
L->length--;
6.线性表的链式存储结构：
①链表的分类：
按实现方式分类 动态链表 静态链表
按链接方式分类 单链表 双链表 循环链表
链式存储结构是一种与顺序存储结构完全不同的线性表实现方法。为了表示每个元素 ai 和其后续元素 ai+1 的关系逻辑，数据元素 ai 除了存储其本身的信息外，还要存储其直接后续的存储位置。这两部分信息组成元素 ai 的存储映象，称为节点。前一部分称为数据域(存放数据元素信息)，后一部分称为指针域(存放后续的存储位置)。因为链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，所以链式存储结构没有顺序存储结构的几个弱点。
下面我们用具体的例子来说明单链表的实际存储结构：
设有某线性表为(English,Math,Chinese,History),四个元素的实际存储地址依次为25，67，124，358，假设其数据域和指针域各占1个字节，则它们在存储器中的实际存储形式为：
头指针
head
由上图，我们可以看出单链表的实际存储结构，为了分析问题的方便，我们采用下面的形式来表示单链表的存储结构：
(1)开始结点English无直接前趋，故应设一个头指针head指向开始结点，head唯一确定一个链表。
(2)终端结点无直接后缀，故其指针域为空NULL,用∧表示。
(3)后一结点的地址存在前一结点的next域中，等价于前一结点的指针指向后一结点。
7.区别几个与指针有关的表示形式：
下面使用C语言描述的单链表：
typedef char DataType;//假设结点的数据域类型是字符
typedef struct node{ //结点类型定义
DataType data; //结点的数据域
Struct node * next;//结点的指针域
}ListNode;
typedef ListNode * LinkList;
ListNode * p;
LinkList head;
这里，LinkList和ListNode * 是不同名字的同一个指针类型，命名的不同是为了概念上个更明确。例如，LinkList类型的指针变量head表示他是单链表的头指针，而ListNode *类型的指针变量p则表示它是指向某一结点的指针。
值得一提的是，我们一定要严格区分指针变量和结点变量这两个概念。例如，以上定义的变量p是类型为ListNode *的指针变量，若p的值非空(p!=NULL)，则它的值是类型为ListNode的某一个结点的地址。通常p所指的结点并非在变量说明部分明显地定义，而是在程序执行过程中，当需要时才产生，故称为动态变量。
下面我们来举个具体的例子来说明一下：
typedef ListNode * p,q;
(1)ListNode*--被定义为一指向ListNode类型的指针。
(2)p,q--被说明为指针变量，是静态变量。当其值非空时，它的值是类型为ListNode的某个结点的地址(指针)。
(3)p*,q*--表示p,q指针所指向的结点变量，是一动态变量(即通过new()函数得到的存储空间，其名字可认为就是p*,q*,能通过free()函数释放。
(4)p=q--p指向q的目标。如下图所示
(a)执行前 (b)执行后
(5)*p=*q--将q所指向的变量(结点)的值赋予p所指向的变量中。
(a)执行前 (b)执行后
在这里，我们可以看出指针类型中所保存的数据是一个变量的地址，而不是变量本身，所以p=q*这样的赋值一般来说是不允许的，因为只将会带来无法预料的后果。所以我们在编写赋值语句的时候，一定要注意只能是指针与指针类型，或者数据类型与数据类型之间的才可以赋值。总而言之，赋值语句中的数据类型一定要匹配。
8.单链表的建立：
假设线性表中结点的数据类型是字符，我们逐个输入这些字符类型的结点，并以换行符'\n'为输入结束标志符。动态建立单链表的常用方法有如下两种：
头插法建表
该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。图志明：在空链表head中依次插入a,b,c之后，将d插入到当前链表表头时指针的修改情况。具体算法如下：
LinkList CreatListF(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)尾插法建表
头插法建立的链表虽然简单，当生成的链表中的结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法链表。该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例如，在空链表head中插入a,b,c之后，将d插入到当前链表的表尾，其指针修改情况如图所示。
尾插法建表算法如下：
LinkList CreateListR(void){
char ch;
LinkList head;
ListNode *s,*r;
head=NULL;r=NULL; //链表初值为空，尾指针初值为空
while((ch=getchar())!='\n'){
s=(ListNode *)malloc(sizeof(ListNode));
s->data=ch;
if(head=NULL)
head=s; //新结点插入空表
else
r->next=x;//新结点插入非空表的尾结点*r之后
r=s; //尾指针指向新表尾
}//end of while
if(r!=NULL)
r->next=NULL; //对于非空表，将尾结点指针域置空
return head;
}
9.单链表中引入头结点的意义
在上述算法中，第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其他位置的插入操作处理是不一样的(实际上对其他操作亦可能如此)，原因是开始结点的位置是存放在头指针(指针变量)中，而其余结点的位置是在其前趋结点的指针域中。因此我们必须对第一个位置上的插入操作做特殊处理，为此上述算法使用了第一个if语句。算法中第二个if语句的作用是为了分别处理空表和非空表这两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点，并称他为头结点，那么会带来以下两个优点：
①由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上操作一致，无须进行特殊处理；
②无论链表是否为空，其头指针是指向头结点的非空指针(空表中头结点的指针域空)，因此空表和非空表的处理也就统一了。本新闻共 6页,当前在第 2页 1 2 3 4 5 6 |
|
|
|
