数据结构--线性表2-2

目录

一、线性表例题： 

二、分配动态内存：

   1.动态创建一个空顺序表的算法：

 2.动态顺序表的插入算法：

3.动态顺序表的删除 

 三、线性表的链式表示和实现

 例题1：创建链表并插入26个字母

例题2：在链表中取第i个数据元素

例题3：在链表中删除一个结点

四、静态链表：

---

一、线性表例题： 

例题1：求两个线性表的“并”，即LA U LB= ？

算法思路：

注意集合并的含义：

LA和LB都是无序表，则从LB种取元素逐一与LA中所有元素比较，相同则不插入LA中；

Void Union(List &LA,List LB)

{//将所有在线性表Lb中但不在La中的数据元素插入到La中

        La_len=Listlength(La);

        Lb_len=Listlength(Lb);

        for(i=1;i<Le_len;i++)

        {

                GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e、

                if(!LocateElem(La,e,equal))

                {

                        ListInsert(La,++La_len,e);

                }

        }

}

算法复杂度分析：LocateElem（La,e,equal) 需La_len次比较

则整个算法需O（La_len×Lb_len） 

 例题2：设正整数a的前驱为PRIOR(a)，后继NEXT(a)，用递归算法计算a+b。

        首先要对加法算法进行描述。不能用简单的加法语句，因为没有加法，要考虑如何用给出的两个特定函数来实现a+b？

思路:  考虑加法的定义，若用数轴来描述a+b，当a不断往"0"移动，b不断往相反方向移动的过程。当a移动到0时，b指向的位置即为a+b。

 （a可视为一减计数器，前移过程中不断递减，而b的后移则是不断加1的过程）

平常我们可以用循环来实现，但根据本题题意不能用循环，而要用递归。

设计要点有二：1.递归算法的形式化描述；2.不能无限制递归，一定要有终止条件。

结果：

int add(int a,int b);

if(a==0)   return(b);

else return (add(prior(a),next(b))); 

若a很大，b很小怎么办？

解决方法：就从小的开始进行减计数。

二、分配动态内存：

（我的C语言专栏中介绍过基础，这里跟数据结构一起编写一些）

#define LIST_INIT_SIZE	100//存储空间的初始分配量 
#define LISTINCREMENT 	10//存储空间的分配增量
Typedef struct{
ElemType *elem;		//表基址（用指针*elem） 
int 	lenght;		//表长度（表中有多少个元素） 
int 	listsize;	//当前分配的表尺寸（字节单位） 
}SqList L; 

   1.动态创建一个空顺序表的算法：

Status InitList_Sq(SqList &L)

{

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

        if(!L.elem) exit(OVERFLOW);//分配失败，结束程序

        L.length=0;                                //暂无元素放入，空表

        L.listsize = LIST_INIT_SIZE;        //表尺寸=初始分配量

        Return       OK;

}//InitList_Sq

 2.动态顺序表的插入算法：

Status ListInsert_Sq(SqList &L,int i,ElemType e)

{//在顺序线性表中第i个位置之前插入新的元素e

    if(i<1||i>L.length+1) return ERROR;//检验i值得合法性

    if(L.length>=L.listsize)//若表长超过表尺寸则要增加尺寸

        {

                newbase = (ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));//realloc（*p，newsize）函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首地址的原空间数据都拷贝进去。

        if(newbase = NULL) exit(OVERFLOW);        //分配失败则退出报错

        L.elem = newbase;                        //重置新基址

        L.listsize = L.listsize +LISTINCREMENT;}//增加表尺寸

        q=&L.elem[i-1];                //q为插入位置。这里没有头结点的情况

        for(p=L.elem[L.length-1];p>=q;--p)  *(p+1)=*p;

//插入位置及之后的元素统统后移，p为元素位置

        *q = e;        //插入e

        ++L.length;        //增加1个数据元素，则表长+1

        return OK;

        }//ListInsert_Sq

}

3.动态顺序表的删除 

Status ListDelete_Sq(SqList &L,int i,ElemType &e) 
{//在顺序表L中删除第i个元素，用e返回其值 if(i<1||L.length) return ERROR;//i值不合法，返回 p=&L.elem[i-1];			//p是被删除元素的位置 e=*p;					//被删除元素的值赋给e q=L.elem+L.length-1;	//q是表尾的位置 for(++p;p<=q;p++)		 *(p-1)=*p;				//待删除元素后面的统统前移--L.length;				//表长-1 return ok;
}//ListDelete_Sq 

 三、线性表的链式表示和实现

1、链表的表示

（1）链式存储结构特点：

其结点在存储器总的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。

设计效率：牺牲空间效率换取时间效率

头指针：是指向链表中第一个结点（或为头结点、或为首结点）的指针；

头结点：是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度；

首元结点：是指链表中存储线性表第一个数据元素a1的结点。 

Typedef struct Lnode{
ElemType  data;		//数据域 
struct Lnode *next;	//指针域 
}Lnode,*LinkList; 	//*LinkList为Lnode类型的指针 

 例题1：创建链表并插入26个字母

#include <stdio.h>
#include <stdlib.h>
typedef struct node{char data;struct node *next;
}node;node *p,*q,*head;
int n;
int m=sizeof(node);void build()		//字母链表的生成。要一个个慢慢链入 
{int i;head=(node*)malloc(m);// p=head;for(i=1;i<26;i++)//因尾结点要特殊处理，故i≠26 {p->data=i+'a'-1;//第一个结点值为字符a p->next=(node*)malloc(m);//为后继结点“挖坑” p=p->next;	//让指针变量p指向后一个结点 }p->data=i+'a'-1;//最后一个元素要单独处理 p->next=NULL;	//单链表尾结点的指针域要置空 } void display()//字母链表的输出 
{p=head;while(p)//当指针不空时循环（仅限于无头结点的情况） {printf("%c",p->data);p=p->next;}} int main(void){build();display();} 

例题2：在链表中取第i个数据元素

Status GetElem_L(Linklist L,int i,ElemType &e)
{//L为带头结点的单链表的头指针//当第i个元素存在时，其值赋给e并返回OK，否则返回error p=L->next;j=1;
//初始化，p指向第一个结点，j为计数器 while(p&&j<i){
//顺指针向后查找，直到p指向第i个元素或p为空 p=p->next;++j;}
//第i个元素不存在 if(!p||j>i) return ERROR;e=p->data;//取第i个元素 return ok;
}GetElem_L

例题3：在链表中删除一个结点

Status ListDelete_L(Linklist &L,int i,ElemType e)
{//在带头结点的单链表L中，删除第i个元素，并由e返回其值 p=L;j=0;while(p->next&&j<i-1){//寻找第i个结点，并令p指向其前驱 p=p->next;++j;} if(!(p->next)p||j>i-1)	return ERROR;//删除不合理位置 q=p->next;p->next=q->next;//删除并释放结点 e=q->data;free(q);return ok;} 

四、静态链表：

        定义一个结构型数组（每个元素都含有数据域和指示域），就可以完全描述链表，指示域就相当于动态链表的指针，称为游标。

静态链表的类型定义如下：

#define MAXSIZE 1000 //预分配最大的元素个数（连续空间）

typedef  struct {

        ElemType  data;        //数据域

        int              cur;          //指示域

}component,SLinkList[MAXSIZE];        //这是一维结构型数组

例题4：利用静态链表存储s=(zhao,qian,sun,li,zhou,wu)。

其原理跟动态差不多，写法类似，知识不需要在使用指针。