2线性表

来自软件实验室
210.44.187.108讨论2016年4月14日 (四) 12:43的版本 头插法

跳转至: 导航搜索

2.1 线性表的定义

概念

线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性,数据元素可以看成是排列在一条线上或一个环上。 线性表分为静态线性表和动态线性表,常见的有顺序表(静态的)、单向链表(动态的)和双向链表(动态的)。 caption

参考资料

[1]

2.2线性表的抽象数据类型

定义

ADT 线性表 (List) Data Operation

   void initList(*L);	//创建并初始化一个空线性表,如果成功返回true,修改表传指针   
   bool listEmpty(L);	//判断一个线性表是否为空,不修改表传值   
   void clearList(*L);	//清空一个线性表,成功返回true   
   bool getElem(L,i,*e);	//从某个位置取出元素并赋值给e(i的范围是[1,L.length]),修改e的值所以传递一个指针,成功返回true  
   int locateElem(L,e);	//查找线性表中是否有e,如果有返回它的位置(从1开始),否则返回0表示失败  
   bool listInsert(*L,i,e);	//插入一个元素e在第i个元素之前(i的取值范围是[1,L.length+1]) ,成功返回true   
   bool listDelete(*L,i,*e);	//删除在第i个位置上的元素(i的取值范围是[1,L.length]),删除的元素赋给e,成功返回true  
   int listLength(L);	//返回线性表的元素个数  

endADT

举例

比如,要实现两个线性表集合A和B的并集操作。即要使得集合A=AUB。说白了,就是把存在集合B中但并不存在A中的数据元素插入到A中即可。

仔细分析一下这个操作,发现我们只要循环集合B中的毎个元素,判断当前元素是否存在A中,若不存在,则插入到A中即可。思路应该是很容易想到的。

void unionL(List *la,List lb){

   int index;  
   int laLength = listLength(*la);	//得到a的长度,需要一个线性表而不是一个地址   
   int lbLength = listLength(lb);}   
   ElemType e;	//声明一个元素   
     
   for(index=1;index<=lbLength;index++){	//遍历lb   
       getElem(lb,index,&e);	//依次得到lb中的元素   
       if(!locateElem(*la,e)){	//检查是否在la中出现   
           listInsert(la,++laLength,e);	//没有出现则插入队尾,前自增!   
       }  
   }  

}

2.3线性表的顺序存储结构

2.3.1定义

线性表的顺序存储是指用一组地址连续的存储单元一次存储线性表的数据元素。在C语言中,可以使用动态数组来实现线性表的顺序存储。

2.3.2顺序存储方式

结构代码示例:

   #define MAXLENGTH 20  /*存储空间初始分配量*/
     
   struct sequencelist  
   {  
       int data[MAXLENGTH];  /*数组存储数据元素,最大值为MAXSIZE*/
       int length;  /*线性表当前长度*/
   };

2.3.3数据长度与线性表长度的区别

2.3.4地址计算方法

2.4线性表顺序存储结构的插入与删除

2.5线性表的链式存储结构

2.6单链表的读取

2.7单链表的插入与删除

2.8单链表的整表创建

实质

创建单链表的过程就是一个动态生成链表的过程,即从“空表”的初始状态起,依次建立各元素节点,并逐个插入链表。

单链表的整表创建的算法思路

1.声明一个节点p和计数器变量i; 2.初始化一个空链表L; 3.让L的头节点的指针指向NULL,即建立一个带头节点的单链表; 4.循环: (1)生成一个新节点赋值给p; (2)随机生成一数字赋值给p的数据域p->date; (3)将p插入到头节点与前一新节点之间。

代码实现

头插法

始终让头节点在第一的位置

代码实现: /* 随机产生n个元素的值,建立带表头结点的单链线性表L(头插法) */

void CreateListHead(LinkList *L, int n)

{

LinkList p;

int i;

srand(time(0)); /* 初始化随机数种子 */

*L = (LinkList)malloc(sizeof(Node));

(*L)->next = NULL; /* 先建立一个带头结点的单链表 */

for (i=0; i < n; i++)

{

p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */

p->data = rand()%100+1; /* 随机生成100以内的数字 */

p->next = (*L)->next;

(*L)->next = p; /* 插入到表头 */

}

} 代码解析: 1. 首先用 *L = (LinkList)malloc(sizeof(Node)); 产生头结点,并使L指向此头结点。再用 (*L)->next = NULL; 即可创建一个带头结点的空链表;

2. 接下来就是循环。新增结点都需要用 (LinkList)malloc(sizeof(Node)); 来开辟内存空间。生成结点 p 之后就给 p 的 data 赋随机值,然后再给 p 的

next 赋值。其实这里也就是用前几天讲到的插入操作了。

头插法.png

完整程序代码:

  1. include "stdio.h"
  1. define OK 1
  1. define ERROR 0
  1. define TRUE 1
  1. define FALSE 0
  1. define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */

typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */

typedef struct Node {

   ElemType data;
   struct Node *next;

}Node;

/* 定义LinkList */

typedef struct Node *LinkList;

/* 初始化顺序线性表 */

Status InitList(LinkList *L) {

   *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
   if(!(*L)) /* 存储分配失败 */
   {
       return ERROR;
   }
   (*L)->next=NULL; /* 指针域为空 */
   return OK;

}

/* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */

int ListLength(LinkList L) {

   int i=0;
   LinkList p=L->next; /* p指向第一个结点 */
   while(p)
   {
       i++;
       p=p->next;
   }
   return i;

}

/* 初始条件:顺序线性表L已存在 */

/* 操作结果:依次对L的每个数据元素输出 */

Status ListTraverse(LinkList L)

{

   LinkList p=L->next;
   while(p)
   {
       visit(p->data);
       p=p->next;
   }
   printf("\n");
   return OK;

}

Status visit(ElemType c)

{

   printf("-> %d ",c);
   return OK;

}

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */

/* 操作结果:用e返回L中第i个数据元素的值 */

Status GetElem(LinkList L,int i,ElemType *e)

{

int j;

LinkList p; /* 声明一结点p */

p = L->next; /* 让p指向链表L的第一个结点 */

j = 1; /* j为计数器 */

while (p && j < i) /* p不为空或者计数器j还没有等于i时,循环继续 */

{

p = p->next; /* 让p指向下一个结点 */

++j;

}

if ( !p || j>i )

return ERROR; /* 第i个元素不存在 */

*e = p->data; /* 取第i个元素的数据 */

return OK; }

/* 初始条件:顺序线性表L已存在 */

/* 操作结果:返回L中第1个与e满足关系的数据元素的位序。 */

/* 若这样的数据元素不存在,则返回值为0 */

int LocateElem(LinkList L,ElemType e) {

   int i=0;
   LinkList p=L->next;
   while(p)
   {
       i++;
       if(p->data==e) /* 找到这样的数据元素 */
               return i;
       p=p->next;
   }
   return 0;

}

/* 随机产生n个元素的值,建立带表头结点的单链线性表L(头插法) */ void CreateListHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; /* 先建立一个带头结点的单链表 */ for (i=0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ p->next = (*L)->next; (*L)->next = p; /* 插入到表头 */ } }

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L), */

/* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */

Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; p = *L; /* 声明一个结点 p,指向头结点 */ j = 1; while (p && j < i) /* 寻找第i个结点 */ { p = p->next; ++j; } if (!p || j > i) return ERROR; /* 第i个元素不存在 */ s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */ s->data = e; s->next = p->next; /* 将p的后继结点赋值给s的后继 */ p->next = s; /* 将s赋值给p的后继 */ return OK; }

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */

/* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 */

Status ListDelete(LinkList *L,int i,ElemType *e) { int j; LinkList p,q; p = *L; j = 1; while (p->next && j < i) /* 遍历寻找第i个元素 */ {

       p = p->next;
       ++j;

} if (!(p->next) || j > i) return ERROR; /* 第i个元素不存在 */ q = p->next; p->next = q->next; /* 将q的后继赋值给p的后继 */ *e = q->data; /* 将q结点中的数据给e */ free(q); /* 让系统回收此结点,释放内存 */ return OK; }

int main() {

   LinkList L;
   Status i;
   int j,k,pos,value;
   char opp;
   ElemType e;
   i=InitList(&L);
   printf("链表L初始化完毕,ListLength(L)=%d\n",ListLength(L));
   printf("\n1.整表创建(头插法) \n2.遍历操作 \n3.插入操作 \n4.删除操作 \n5.获取结点数据 \n6.查找某个数是否在链表中 \n0.退出 \n请选择你的操作:\n");
   while(opp != '0'){
       scanf("%c",&opp);
       switch(opp){
           case '1':
               CreateListHead(&L,10);
               printf("整体创建L的元素(头插法):\n");
               ListTraverse(L);
               printf("\n");
               break;
           case '2':
               ListTraverse(L);
               printf("\n");
               break;
           case '3':
               printf("要在第几个位置插入元素?");
               scanf("%d",&pos);
               printf("插入的元素值是多少?");
               scanf("%d",&value);
               ListInsert(&L,pos,value);
               ListTraverse(L);
               printf("\n");
               break;
           case '4':
               printf("要删除第几个元素?");
               scanf("%d",&pos);
               ListDelete(&L,pos,&e);
               printf("删除第%d个元素成功,现在链表为:\n", pos);
               ListTraverse(L);
               printf("\n");
               break;
           case '5':
               printf("你需要获取第几个元素?");
               scanf("%d",&pos);
               GetElem(L,pos,&e);
               printf("第%d个元素的值为:%d\n", pos, e);
               printf("\n");
               break;
           case '6':
               printf("输入你需要查找的数:");
               scanf("%d",&pos);
               k=LocateElem(L,pos);
               if(k)
                   printf("第%d个元素的值为%d\n",k,pos);
               else
                   printf("没有值为%d的元素\n",pos);
               printf("\n");
               break;
           case '0':
               exit(0);
       }
   }

}

尾插法

让新节点每次都插在终端节点的后面

代码实现: /* 随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法) */ void CreateListTail(LinkList *L, int n) { LinkList p,r; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */ r=*L; /* r为指向尾部的结点 */ for (i=0; i < n; i++) { p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ r->next=p; /* 将表尾终端结点的指针指向新结点 */ r = p; /* 将当前的新结点定义为表尾终端结点 */ } r->next = NULL; /* 表示当前链表结束 */ } 完整程序代码:

  1. include "stdio.h"
  1. define OK 1
  2. define ERROR 0
  3. define TRUE 1
  4. define FALSE 0

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */

typedef struct Node {

   ElemType data;
   struct Node *next;

}Node; typedef struct Node *LinkList; /* 定义LinkList */

Status visit(ElemType c) {

   printf("%d ",c);
   return OK;

}

/* 初始化顺序线性表 */ Status InitList(LinkList *L) {

   *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
   if(!(*L)) /* 存储分配失败 */
           return ERROR;
   (*L)->next=NULL; /* 指针域为空 */
   return OK;

}

/* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */ int ListLength(LinkList L) {

   int i=0;
   LinkList p=L->next; /* p指向第一个结点 */
   while(p)
   {
       i++;
       p=p->next;
   }
   return i;

}

/* 初始条件:顺序线性表L已存在 */ /* 操作结果:依次对L的每个数据元素输出 */ Status ListTraverse(LinkList L) {

   LinkList p=L->next;
   while(p)
   {
       visit(p->data);
       p=p->next;
   }
   printf("\n");
   return OK;

}

/* 随机产生n个元素的值,建立带表头结点的单链线性表L(头插法) */ void CreateListHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; /* 先建立一个带头结点的单链表 */ for (i=0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ p->next = (*L)->next; (*L)->next = p; /* 插入到表头 */ } }

/* 随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法) */ void CreateListTail(LinkList *L, int n) { LinkList p,r; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */ r=*L; /* r为指向尾部的结点 */ for (i=0; i < n; i++) { p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ r->next=p; /* 将表尾终端结点的指针指向新结点 */ r = p; /* 将当前的新结点定义为表尾终端结点 */ } r->next = NULL; /* 表示当前链表结束 */ }

int main() {

   LinkList L;
   Status i;
   char opp;
   i=InitList(&L);
   printf("初始化L后:ListLength(L)=%d\n",ListLength(L));
   printf("\n1.查看链表 \n2.创建链表(尾插法) \n3.链表长度 \n0.退出 \n请选择你的操作:\n");
   while(opp != '0'){
       scanf("%c",&opp);
       switch(opp){
           case '1':
               ListTraverse(L);
               printf("\n");
               break;
           case '2':
               CreateListTail(&L,20);
               printf("整体创建L的元素(尾插法):\n");
               ListTraverse(L);
               printf("\n");
               break;
           case '3':
               //clearList(pHead);   //清空链表
               printf("ListLength(L)=%d \n",ListLength(L));
               printf("\n");
               break;
           case '4':
               printf("\n");
               break;
           case '0':
               exit(0);
       }
   }

}

2.9单链表的整表删除