线性表的链式存储

头文件如下

//LinkList.h


#ifndef LINKLIST_H
#define LINKLIST_H

#define OK 1
#define ERROR 0;
typedef int Status;
typedef int ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode *next;
}LNode,* LinkList;

Status GetElem(LinkList L, int i, ElemType &e);
Status ListInsert(LinkList &L, int i, ElemType e);
Status ListDelete(LinkList &L, int i, ElemType &e);
void CreateList(LinkList &L, int n);
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc);
void ListTraverse(LinkList &L);

#endif

链表操作的实现

  1 //LinkList.cpp
  2 
  3 #include"LinkList.h"
  4 #include<iostream>
  5 #include<cstdlib>
  6 
  7 Status GetElem(LinkList L, int i, ElemType &e)
  8 {
  9     LinkList p;
 10     p = L->next;
 11     int j = 1;
 12     while (p&&(j < i)) {
 13         p = p->next;
 14         ++j;
 15     }
 16     if (!p || j > i)
 17         return ERROR;
 18     e = p->data;
 19     return OK;
 20 }
 21 
 22 //当需要改变LinkList的值的时候，需要&引用
 23 Status ListInsert(LinkList &L, int i, ElemType e)
 24 //在带头结点的单链表中第i个位置之前插入元素e
 25 {
 26     LinkList p;
 27     p = L;
 28     int j = 0;
 29     while (p&&j < i - 1)
 30     {
 31         p = p->next;
 32         ++j;
 33     }
 34     if (!p || j > i - 1)
 35         return ERROR;
 36     LinkList s = (LinkList)malloc(sizeof(LNode));
 37     s->data = e;
 38     s->next = p->next;
 39     p->next = s;
 40     return OK;
 41 }
 42 
 43 Status ListDelete(LinkList &L, int i, ElemType &e)
 44 //在带头节点的单链表L中，删除第i个元素，并由e返回其值
 45 {
 46     LinkList p = L;
 47     int j = 0;
 48     while (p->next&&j < i - 1) {//寻找第i个节点，并令p指向其前趋
 49         p = p->next;
 50         ++j;
 51     }
 52     if (!(p->next) || j > i - 1)
 53         return ERROR;
 54     LinkList q = p->next;     //删除并释放结点
 55     p->next = q->next;
 56     e = q->data;
 57     free(q);
 58     return OK;
 59 }
 60 
 61 void CreateList(LinkList &L, int n)
 62 //逆序输入n个元素的值，建立带表头结点的单链线性表L.
 63 {
 64     L = (LinkList)malloc(sizeof(LNode));
 65     L->next = NULL;    //建立一个带表头结点的单链表
 66     if(n>0)
 67         std::cout << "逆序输入链表元素值: " << std::endl;
 68     for (int i = n; i > 0; --i)
 69     {
 70         LinkList p = (LinkList)malloc(sizeof(LNode));//生成新结点
 71         std::cin >> p->data;
 72         p->next = L->next;
 73         L->next = p;//插入到表头
 74     }
 75 }
 76 
 77 void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc)
 78 //要求单链线性表La和Lb的元素按非递减排列
 79 //归并La和Lb得到新的的单链线性表Lc，Lc的元素也按值
 80 {
 81     LinkList pa = La->next;
 82     LinkList pb = Lb->next;
 83     LinkList pc = Lc=La;        //将La的头结点作为Lc的头结点
 84     while (pa&&pb)
 85     {
 86         if (pa->data <= pb->data)
 87         {
 88             pc->next = pa;
 89             pc = pa;
 90             pa = pa->next;
 91         }
 92         else
 93         {
 94             pc->next = pb;
 95             pc = pb;
 96             pb = pb->next;
 97         }
 98     }
 99     pc->next = pa ? pa : pb;
100     free(Lb);
101 }
102 
103 void ListTraverse(LinkList &L)
104 {
105     LinkList q = L;
106     q = q->next;
107     while (q)
108     {
109         std::cout << q->data<<"  ";
110         q = q->next;
111     }
112     std::cout << std::endl;
113 }

主函数实现

//Main.cpp

#include"LinkList.h"
#include<iostream>
using namespace std;

int main()
{
    LinkList La;
    LinkList Lb;
    LinkList Lc;

    CreateList(La, 4);
//    CreateList(Lb, 3);

//    ListTraverse(La);
//    ListTraverse(Lb);

//    MergeList(La, Lb, Lc);

//    cout << "Lc: ";
//    ListTraverse(Lc);

    LinkList L;
    ElemType n1 = 1;
    ElemType n2 = 2;
    ElemType n3 = 3;
    ElemType n4 = 4;
    ElemType n5 = 5;
    ElemType n6 = 6;
    ElemType n7 = 7;
    ElemType n8 = 8;
    ElemType n9 = 9;
    ElemType n0 = 0;
    ElemType temp = 0;

    ListInsert(La, 2, n9);
    ListTraverse(La);

    CreateList(L, 0);
    ListInsert(L, 1, n7);
    ListInsert(L, 2, n9);
    ListTraverse(L);


    system("pause");
    return 0;
}