线性表的链式存储和实现

　　存储结构分为两种，线性表的这两种存储结构在时间复杂度上各有特色，若在操作中涉及遍历、查找较多的话，则宜用顺序存储结构；若涉及插入、删除较多的话，则宜用链式存储；具体选择哪一种存储结构要根据需要进行的操作来分析。
　　下面分享链式存储实现的代码，希望对你的学习有帮助
　　// 测试.cpp : 定义控制台应用程序的入口点。
　　//
　　#include "stdafx.h"
　　#include "stdlib.h"
　　#include "iostream"
　　using namespace std;
　　typedef struct LNode {
　　int data;
　　struct LNode *next;
　　}LinkList;
　　LinkList *p， *q， *head;
　　//链表的初始化
　　void InitList(LinkList &L)
　　{
　　head = (LinkList *)malloc(sizeof(LinkList));
　　if (head==NULL)
　　{
　　exit(0);
　　}
　　head->next = NULL;
　　}
　　//在链表尾部插入值
　　void InsertLastList(LinkList &L， int e)
　　{
　　p = q = (LinkList *)malloc(sizeof(LinkList));
　　p = head;
　　if (p==NULL)
　　{
　　exit(0);
　　}
　　while (p->next!=NULL)
　　{
　　p = p->next;
　　}
　　q->data = e;
　　q->next = p->next;//NULL
　　p->next = q;
　　}
　　//在链表头部插入值
　　void InsertFirstList(LinkList &L， int e)
　　{
　　p = (LinkList *)malloc(sizeof(LinkList));
　　if (head==NULL)
　　{
　　exit(0);
　　}
　　p->data = e;
　　p->next = head->next;
　　head->next = p;
　　}
　　//遍历链表
　　void ShowList(LinkList L)
　　{
　　p = (LinkList *)malloc(sizeof(LinkList));
　　p = head->next;
　　if (p==NULL)
　　{
　　exit(0);
　　}
　　while (p!=NULL)
　　{
　　cout << p->data << " ";
　　p = p->next;
　　}
　　cout << endl;
　　}
　　//返回链表的长度
　　int ListLength(LinkList L)
　　{
　　int count = 0;
　　p = (LinkList *)malloc(sizeof(LinkList));
　　p = head;
　　while (p->next!=NULL)
　　{
　　count++;
　　p = p->next;
　　}
　　return count;
　　}
　　//用e返回第i个结点
　　void GetElem(LinkList L， int i， int &e)
　　{
　　int j = 1;
　　p = (LinkList *)malloc(sizeof(LinkList));
　　p = head->next;
　　while (p&&j<i)
　　{ 
　　p = p->next;
　　j++;
　　}
　　if (!p||j>i)
　　{
　　exit(0);
　　}
　　else
　　{
　　e = p->data;
　　}
　　free(p);
　　}
　　//在i位置插入e结点
　　void ListInsert(LinkList &L， int i， int e)
　　{
　　p = head;
　　int j = 0;
　　while (p&&j<i-1)
　　{
　　p = p->next;
　　++j;
　　}
　　if (!p||j>i-1)//第i个元素不存在
　　{
　　exit(0);
　　}
　　q = (LinkList *)malloc(sizeof(LinkList));
　　q->data = e;
　　q->next = p->next;
　　p->next = q;
　　}
　　//删除第i个结点
　　void ListDelete(LinkList &L， int i，int &e)
　　{
　　p = head;
　　int j = 0;
　　while (p&&j<i-1)
　　{
　　p = p->next;
　　++j;
　　}
　　if (!p||j>i-1)
　　{
　　exit(0);
　　}
　　q=p->next;
　　p->next = q->next;
　　e = q->data;
　　free(q);
　　}
　　//销毁链表
　　void DestroyList(LinkList &L)
　　{
　　q = p = (LinkList *)malloc(sizeof(LinkList));
　　p = head;
　　q = p->next;
　　while (q!=NULL)
　　{
　　free(p);
　　p = q;
　　q = p->next;
　　}
　　free(q);
　　}
　　int main()
　　{
　　LinkList L;
　　InitList(L);
　　int num[6] = { 0，5，3，4，7，3 };
　　for (size_t i = 0; i < sizeof(num)/sizeof(num[0]); i++)
　　{
　　InsertLastList(L， num[i]);
　　}
　　ShowList(L);
　　InsertFirstList(L， 1);
　　ShowList(L);
　　cout << ListLength(L) << endl;
　　ListInsert(L， 2， 99);
　　int e;
　　ListDelete(L， 2， e);
　　ShowList(L);
　　DestroyList(L);
　　return 0;
　　}