『数据结构』线性表链式存储(链表)-单链表

数据结构–线性表链式存储(链表)–单链表

定义：

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以节点来表示的，每个结点的构成：元素( 数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

链表特点：

根据线性表的长度动态的申请存储空间，以解决顺序存储中存在的存储空间难以确定的问题。

元素的要素：

1. 指针：指向下一个元素。

2. 值：当前元素储存的数据。

   #include<bits/stdc++.h>
   using namespace std;
   template
   struct Node //节点类
   {
   T data;
   Node *next; //此处也可以省略
   };
   template
   class LinkList
   {
   Node *first; // 单链表的头指针 , 可以省略
   int length;
   public:
   LinkList ( )
   {
   first=new Node;
   first -> next= NULL ;
   length=0;
   }
   LinkList ( T a[ ], int n ) ;
   LinkList ( T a[ ], int n,int w) ;
   ~LinkList ( ) ;
   int get_Len( )
   {
   return length;
   };
   T get_Loc ( int i ) ;
   int ser_Loc ( T x ) ;
   void ins_Loc ( int i, T x ) ;
   T del_Loc ( int i ) ;
   void print_List ( ) ;
   };
   template
   LinkList:: LinkList(T a[ ], int n)
   {
   first=new Node; //生成头结点
   first->next=NULL;
   Node *s;
   for (int i=0; i<n; i++)
   {
   s=new Node;
   s->data=a[i]; //为每个数组元素建立一个结点
   s->next=first->next;
   first->next=s;
   }
   length=n;
   }
   template
   LinkList:: LinkList(T a[ ], int n,int w) //w并无实际意义，用于区分头插法于尾插法
   {
   Node *r,*s; //尾指针
   first=new Node; //生成头结点
   r=first;
   for (int i=0; i<n; i++)
   {
   s=new Node;
   s->data=a[i]; //为每个数组元素建立一个结点
   r->next=s;
   r=s; //插入到终端结点之后
   }
   r->next=NULL; //单链表建立完毕，将终端结点的指针域置空
   length=n;
   }
   template
   void LinkList:: print_List()
   {
   Node *p;
   p=first->next;
   while(p)
   {
   cout<data;
   p=p->next;
   }
   }
   template
   T LinkList::get_Loc(int i)
   {
   Node *p;
   int j;
   p=first->next;
   j=1; //或p=first; j=0;
   for(int j=0;p && j<i-1;j++)
   {
   p=p->next; //工作指针p后移
   j++;
   }
   if (!p)
   throw “位置非法”;
   else
   return p->data;
   }
   template
   void LinkList::ins_Loc(int i, T x)
   {
   Node *p;
   int j;
   p=first ;
   j=0; //工作指针p初始化
   for(int j=0;p && j<i-1;j++)
   {
   p=p->next; //工作指针p后移
   j++;
   }
   if (!p)
   throw “位置非法”;
   else
   {
   Node *s;
   s=new Node;
   s->data=x; //向内存申请一个结点s，其数据域为x
   s->next=p->next; //将结点s插入到结点p之后
   p->next=s;
   }
   }
   template
   T LinkList::del_Loc(int i)
   {
   Node *p;
   p=first ; //工作指针p初始化
   for(int j=0;p && j<i-1;j++) //查找第i-1个结点
   {
   p=p->next;
   j++;
   }
   if (!p || !p->next)
   throw “位置非法”; //结点p不存在或结点p的后继结点不存在
   else
   {
   Node *q;
   T x;
   q=p->next;
   x=q->data; //暂存被删结点
   p->next=q->next; //摘链
   delete q;
   return x;
   }
   }
   template
   LinkList:: ~LinkList()
   {
   Node *q;
   while (first)
   {
   q=first->next;
   delete first;
   first=q;
   }
   length=0;
   }
   int main()
   {
   //具体操作，不与给出
   }