数据结构--线性表

专题--线性表

　　线性表的存储方式有：顺序存储和链式存储，对应顺序表和链式表。
　　链式表又分为：单链表和双向链表。
  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <ctime>
  4 using namespace std;
  5 
  6 //单链表
  7 struct Node
  8 {
  9     int data;   //数据域
 10     Node *next; //指针域
 11 };
 12 typedef Node *LinkList;
 13 //取点
 14 bool GetElem(LinkList L,int i,int *e)
 15 {
 16     int j=1;
 17     Node *p=L->next;     //有头结点
 18     while(p&&j<i)
 19     {
 20         p=p->next;
 21         ++j;
 22     }
 23     if(!p||j>i)
 24         return false;
 25     *e=p->data;
 26     return true;
 27 }
 28 //插入，在第i个节点之前插入
 29 bool ListInsert(LinkList *L,int i,int e)
 30 {
 31     Node *p=*L;   //有头结点
 32     int j=1;
 33     while(p&&j<i) //寻找第i-1个节点
 34     {
 35         p=p->next;
 36         ++j;
 37     }
 38     if(!p||j>i)
 39         return false;
 40     Node *s=new Node;
 41     s->data=e;
 42     s->next=p->next;
 43     p->next=s;
 44     return true;
 45 }
 46 //删除
 47 bool ListDelete(LinkList *L,int i,int *e)
 48 {
 49     Node *p=*L;
 50     int j=1;
 51     while(p->next&&j<i)
 52     {
 53         p=p->next;
 54         ++j;
 55     }
 56     if(!(p->next)||j>i)
 57         return false;
 58     Node *q=p->next;          //最终删除q
 59     p->next=q->next;
 60     *e=q->data;
 61     delete q;
 62     return true;
 63 }
 64 //整表创建
 65 void CreateList(LinkList *L,int n)
 66 {
 67     srand(time(0));
 68     *L=new Node;       //创建头结点
 69     (*L)->next=nullptr;
 70 
 71     Node *p=nullptr;
 72     for(int i=0;i<n;++i)
 73     {
 74         p=new Node;
 75         p->data=rand()%100+1;
 76         //头插
 77         p->next=(*L)->next;
 78         (*L)->next=p;
 79     }
 80 }
 81 void CreateList1(LinkList *L,int n)
 82 {
 83     srand(time(0));
 84     *L=new Node;
 85     Node *r=*L;
 86     Node *p=nullptr;
 87     for(int i=0;i<n;++i)
 88     {
 89         p=new Node;
 90         p->data=rand()%100+1;
 91         //尾插
 92         r->next=p;
 93         r=p;
 94     }
 95     r->next=nullptr;
 96 }
 97 //整表删除
 98 bool ClearList(LinkList *L)
 99 {
100     Node *p=(*L)->next;  //p指向第一个节点
101     Node *q=nullptr;
102     while(p)
103     {
104         q=p->next;
105         delete p;
106         p=q;
107     }
108     (*L)->next=nullptr;  //头结点指针域置为空
109     return true;
110 }
111 /*************/
112 //双向链表
113 struct DNode
114 {
115     int data;     //数据域
116     DNode *prev;  //前驱
117     DNode *next;  //后继
118 };
119 typedef DNode *DLinkList;
120 /*插入
121 s->prior=p;
122 s->next=p->next;
123 p->next->prior=s;
124 p->next=s;
125 */
126 /*删除
127 p->prior->next=p->next;
128 p->next->prior=p->prior;
129 */