线性表

(1) 线性表的定义

线性表(linear list)是由n个数据类型相同的有序元素所组成的集合,n称为线性表的长度. 对线性表的常见运算有创建空表,判空,判满,搜索,插入,删除和输出等.

(2) 线性表 ADT

ADT LinearList 数据: n个数据类型相同的有序元素所组成的集合,n称为线性表的长度 运算: Create() 创建一个线性表 IsEmpty() 判空:若线性表为空,则返回 1,否则 返回 0; IsFull() 判满:若线性表满,则返回 1,否则 返回 0; Search() 搜索:在线性表中搜索某元素,若找到,返回它的下标,否则返回 -1; Insert() 插入:将某元素出入线性表中. Delete() 删除:将线性表中某元素删除. Disply() 输出:输出线性表元素.

(3)线性表的数组实现

定义数组a[MaxSize]用来存储线性表元素, MaxSize是允许最大容量, 用n表示所含元素的个数. 也这种线性表称为顺序表(sequence list) Delete() 删除:将线性表中某元素删除. 要考虑四种情况: (1) 顺序表为空表. (2) 顺序表非空,下标pos超限(pos<0 或 pos>n-1) (3) 顺序表非空,下标pos未超限,pos是表尾元素下标 (4) 顺序表非空,下标pos未超限,pos是非表尾元素下标 Insert() 插入:将某元素出入线性表中. 要考虑三种不同的情况: (1) 顺序表满 (2) 顺序表未满,插入位置不在表中. (当pos不在表中时,约定pos=-1,将x插入表头) (3) 顺序表未满,插入位置在表中.

线性表应用举例

集合A和B的并集(A∪B)

//集合A和B的并集(A∪B) void Union(SeqList &A,SeqList B){ int x; for(int i=0;i<B.n;i++){ x=B.a[i]; if(Search(A,x)==-1) Insert(A,A.n-1,x); } }

集合A和B的交集(A∩B)

//集合A和B的交集(A∩B) void Intersection(SeqList &A,SeqList B){ int x,pos; for(int i=0;i<A.n;i++){ x=A.a[i]; if(Search(B,x)){ pos = Search(A,x); Delete(A,pos); i--; } } } #include<iostream> using namespace std; #define MaxSize 5 //顺序表的最大容量 struct SeqList{ int a[MaxSize]; int n; }; //创建空顺序表 void Create(SeqList &L){ L.n = 0; } //判空 int IsEmpty(SeqList L){ if(L.n == 0) return 1; else return 0; } //判满 int IsFull(SeqList L){ if(L.n >= MaxSize) return 1; else return 0; } //搜索 int Search(SeqList L,int x){ int pos = -1; for(int i = 0;i<L.n;i++){ if(L.a[i] == x){ pos = i; break; } } return pos; } //插入 void Insert(SeqList &L,int pos,int x){ //如果pos=-1,将x插入a[0],否则将插入a[pos]之后 if(IsFull(L)){ cout<<"顺序表满,无法插入"<<endl; return; } if(pos){ for(int i=L.n;i>pos+1;i--) //元素a[n-1],a[n-2]...a[pos+1]一次向后移 L.a[i]=L.a[i-1]; L.a[pos+1]=x; L.n++; } else{ for(int i=L.n;i>0;i--) L.a[i]=L.a[i-1]; L.a[0]=x; L.n++; } } //删除 void Delete(SeqList &L,int pos){ if(IsEmpty(L)){ cout<<"顺序表空,无法删除"<<endl; return; } if(pos<0||pos>L.n-1){ cout<<"顺序表中无此元素"<<endl; return; } if(pos == L.n-1) L.n--; else{ for(int i=pos;i<L.n-1;i++) L.a[i]=L.a[i+1]; L.n--; } } //输出 void Display(SeqList L){ if(IsEmpty(L)){ cout<<"顺序表空,无元素输出"<<endl; return; } for(int i= 0;i < L.n;i++) cout<<L.a[i]<<" "; cout<<endl; } int main(){ SeqList L; Create(L); Insert(L,-1,3); Display(L); Insert(L,-1,2); Display(L); Insert(L,-1,1); Display(L); int pos; pos=Search(L,3); Insert(L,pos,4); Display(L); Delete(L,pos); Display(L); }

(4) 线性表的链表现实

利用单链表来创建线性表,称为链表(link list), 可以随意改变链表的长度, 空链表用 head = NULL来表示. 而判满函数IsFull()和线性表长度n可以忽略. 在插入或删除结点时,链表中的其他结点不需要做移动操作. #include<iostream> using namespace std; //结点定义 struct Node{ int data; Node *next; }; //链表定义 struct LinkList{ Node *head; }; //创建链表 void Create(LinkList &L){ L.head=NULL; } //判空 int IsEmpty(LinkList L){ if(L.head == NULL) return 1; else return 0; } //搜索x结点的地址 Node *Search(LinkList L,int x){ int flag=0; Node *p=L.head; while(p!=NULL){ if(p->data==x){ flag=1; break; } p=p->next; } if(flag==0) return NULL; else return p; } //插入 void Insert(LinkList &L,Node *posNode,int x){ Node *NewNode; NewNode = new Node; NewNode->data = x; NewNode->next = NULL; if(IsEmpty(L)) L.head=NewNode; else{ if(posNode == NULL){ NewNode->next = L.head; L.head = NewNode; }else{ NewNode->next=posNode->next; posNode->next=NewNode; } } } //删除 void Delete(LinkList &L,Node *DelNode){ Node *p; if(IsEmpty(L)){ cout<<"链表为空"<<endl; return; } if(DelNode == NULL){ cout<<"链表中无此结点"<<endl; return; } if(DelNode == L.head){ if(L.head->next != NULL){ L.head = L.head->next; delete DelNode; }else{ L.head = NULL; delete DelNode; } }else{ p=L.head; while(p->next!=DelNode) p=p->next; p->next = DelNode->next; delete DelNode; } } //输出单链表 void Display(LinkList L){ //输出单链表 if(IsEmpty(L)){ cout<<"链空,无节点输出"<<endl; return; } Node *p=L.head; //探测指针p while(p!=NULL){ cout<<p->data<<"=>"; p=p->next; } cout<<"NULL"<<endl; } int main(){ LinkList L; Create(L); Insert(L,NULL,3); Display(L); Insert(L,NULL,2); Display(L); Insert(L,NULL,1); Display(L); Node *posNode,*DelNode; posNode=Search(L,3); Insert(L,posNode,4); Display(L); posNode=Search(L,4); Insert(L,posNode,5); Display(L); DelNode=Search(L,1); Delete(L,DelNode); Display(L); DelNode=Search(L,5); Delete(L,DelNode); Display(L); DelNode=Search(L,3); Delete(L,DelNode); Display(L); return 0; }

写于2020-10-22