常用的数据结构实例

1.栈

1.1.栈的顺序存储结构

1.1.1 C语言版

1.操作要点：

（1）对于顺序栈，如栈时，首先判断栈是否满了，栈满的条件是：s->top == MAXSIZE-1,栈满时不能入栈；否则出现空间溢出，引起错误，称为上溢。

（2）出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误，通常栈空时常作为一种控制转移条件。

　　（3）取栈顶元素与出栈的不同之处是出栈操作改变栈顶指针top的位置（栈顶指针下移一个位置），而取栈顶元素操作只是读出栈顶元素的值，栈顶指针top的位置不变。

2.顺序栈的类型描述

1 #define MAXSIZE  10
2 typedef int Emptype;
3 typedef int Decltype;
4 typedef struct node
5 {
6     Decltype data[MAXSIZE];
7     int top;
8 }SeqStack ,*Stack;
9 SeqStack *s;  //定义顺序栈指针

3.置空栈

1 SeqStack *Init_SeqStac()
2 {
3     SeqStack *s;
4     s = (Stack)malloc(sizeof(SeqStack));
5     s->top = -1;
6     return s;
7 }

4.判空栈

1  int Empty_SeqStack(SeqStack *s)
2  {
3      if (s->top == -1) return 1;
4      else return 0;
5  }

5.入栈

 1 int Push_SeqStack(SeqStack *s, Decltype x)
 2 {
 3     if (s->top == MAXSIZE - 1) 
 4         return 0;
 5     else
 6     {
 7         s->top++;
 8         s->data[s->top] = x;
 9         return 1;
10     }
11 }

6.出栈

 1 int Pop_SeqStack(SeqStack *s, Decltype *x)
 2 {
 3     if (Empty_SeqStack(s))
 4         return 0;
 5     else
 6     {
 7         *x = s->data[s->top];
 8         s->top--;
 9         return 1;
10     }
11 }

7.取栈顶元素

1 Decltype Top_SeqStack(SeqStack *s)
2 {
3     if (Empty_SeqStack(s))
4     return 0;
5     else
6         return (s->data[s->top]);
7 
8 }

8.两栈共享数据结构的定义

 1 typedef struct
 2 {
 3     Emptype stack][MAXSIZE];
 4     int lefttop;  //左栈栈定位置
 5     int righttop;  //右栈栈顶位置
 6 }dupsqstack;
 7 
 8 //设定左右栈标志
 9 char status;
10 status = 'L';
11 status = 'R';

9.判断共享栈满

1 1 s->lefttop + 1 == s->righttop;

10.共享栈初始化操作

1 int initDupStack(dupsqstack *s)
2 {
3     if ((s = (dupsqstack*)malloc(sizeof(dupsqstack))) == NULL)
4         return false;
5     s->lefttop - 1;
6     s->righttop = MAXSIZE
7         return true;
8 }

11.共享栈入栈操作

 1 int pushDupsqstack(dupsqstack *s, char status, Emptype x)
 2 {
 3     //把数据元素x压入左栈或右栈
 4     if (s->lefttop + 1 == s->righttop)
 5         return false;
 6     if (status = 'L')
 7         s->stack[++s->righttop] = x;
 8     else if (status = 'R')
 9         s->stack[--s->lefttop] = x;
10     else return false;
11     return true;
12 }

12.共享栈出栈操作

 1 Emptype popDupsqstack(dupsqstack *s, char status)
 2 {
 3     //从左栈或右栈栈顶退出元素
 4     if (status = 'L')
 5     {
 6         if (s->lefttop < 0)
 7             return NULL;
 8         else return (s->stack[s->lefttop--]);
 9     }
10     else if (status = 'R')
11     {
12         if (s->righttop >MAXSIZE-1)
13             return NULL;
14         else return (s->stack[s->righttop++]);
15     }
16     else return NULL;
17 }

1.1.2 java版

　　原理不再描述，只上代码

package com.test;
/**
 * @author Administrator
 * @param <T>
 * 在java中，用数组表示栈
 */
public class SqStack<T> {
    private T data[];  //栈
    private int top;   //栈顶指针,也是数组下标
    private int maxSize; //栈的大小，也是数组的大小
    
    //初始化栈
    public SqStack(int maxSize){
        this.maxSize = maxSize;
        this.top = -1;   
        this.data = (T[]) new Object[maxSize];
    }
    
    //1.判栈空，如果站顶指针还不是数组下标中的一个，则为空
    public boolean isNull(){
        if(this.top < 0){
            return true;
        }else{
            return false;
        }
    }
    //2.判栈满,如果站顶指针达到数组最大值，则为满
    public boolean isFull(){
        if(this.top == this.maxSize - 1){
            return true;
        }else{
            return false;
        }
    }
    //3.入栈,给数组中加入元素
    public boolean push(T value){
        if(isFull()){
            return false;
        }else{
            data[++top] = value;
            return true;
        }
    }
    
    //4.出栈
    public T Pop(){
        if(isNull()){
            return null;
        }else{
            T value = data[this.top];
            --this.top;
            return value;
        }
    }
    
}

View Code

package com.test;

public class TestStack {
    public static void main(String[] args) {
       SqStack<Integer> s = new SqStack<Integer>(5);
       System.out.println(s.isFull());
       System.out.println(s.isNull());
       s.push(new Integer(1));
       s.push(new Integer(2));
       s.push(new Integer(3));
       s.push(new Integer(4));
       s.push(new Integer(5));
       s.push(new Integer(6));
       System.out.println(s.Pop());
       System.out.println(s.Pop());
       System.out.println(s.Pop());
       System.out.println(s.Pop());
       System.out.println(s.Pop());
       System.out.println(s.Pop());
    }
}

View Code

运行结果：

false
true
5
4
3
2
1
null

1.2.栈的链式存储结构

1.2.1 C语言版

1.要点：

　　（1）链栈是避免栈出现上溢的最好的存储方法。

　　（2）栈底在链表的最后一个结点，栈顶是链表的第一个结点。

　　（3）一个链栈可由栈顶指针唯一确定。

　　（4）要采用带头结点的单链表实现链栈，因为插入和删除操作仅限在表头位置进行。

　　（5）当top->next == NULL时，代表链栈为空。

2.链栈的定义

1 typedef struct Stacknode
2  {
3      Emptype data;
4      struct Stacknode *next;
5 }slStacktype;

3.链栈的入栈操作

 1 int pushLstack(slStacktype *top, Emptype x)
 2 {
 3     //将元素x压入链栈top中
 4     slStacktype *p;
 5     if ((p = (slStacktype *)malloc(sizeof(slStacktype))) == NULL)
 6         return false;
 7     p->data = x;
 8     p->next = top->next;
 9     top->next = p;
10     return true;
11 }

4.链栈的出栈操作

 1 Emptype popLstack(slStacktype *top)
 2 {
 3     slStacktype *p;
 4     Emptype x;
 5     if (top->next == NULL)
 6         return false;
 7     p = top->next;
 8     top->next = p->next;
 9     x = p->data;
10     free(p);
11     return x;
12 }

5.多个链栈入栈操作

 1 int pushLstack(slStacktype *top[M],int i, Emptype x)
 2 {
 3     //将元素x压入链栈top[i]中
 4     slStacktype *p;
 5     if ((p = (slStacktype *)malloc(sizeof(slStacktype))) == NULL)
 6         return false;
 7     p->data = x;
 8     p->next = top[i]->next;
 9     top[i]->next = p;
10     return true;
11 }

6.多个链栈出栈操作

 1 Emptype popLstack(slStacktype *top[M], int i)
 2 {
 3     slStacktype *p;
 4     Emptype x;
 5     if (top[M]->next == NULL)
 6         return false;
 7     p = top[i]->next;
 8     top[i]->next = p->next;
 9     x = p->data;
10     free(p);
11     return x;
12 }

7.部分测试

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 //定义栈
 4 typedef struct node
 5 {
 6     int data;
 7     struct node *next;
 8 } *LinkSatck;
 9 
10 
11 //入栈
12 LinkSatck Push(LinkSatck top,int x)
13 {
14     LinkSatck newp = (LinkSatck)malloc(sizeof(LinkSatck));
15     if (newp != NULL)
16     {
17         newp->data = x;
18         newp->next = top->next;
19         top->next = newp;
20     }
21     else
22         printf("内存已满
");
23     return top;
24 
25 }
26 //出栈
27 int Pop(LinkSatck top)
28 {
29     LinkSatck temp;
30     int t;
31     if (top->next == NULL)
32         printf("栈空
");
33     else
34     {
35         temp = top->next;
36         t = temp->data;
37         top->next = temp->next;
38         free(temp);
39         
40     }
41     return t;
42     
43 }
44 //打印
45 void print(LinkSatck top)
46 {
47     if (top->next==NULL)
48         printf("栈空
");
49     else
50     {
51         while (top->next != NULL)
52         {
53             printf("%3d", top->next->data);
54             top=top->next ;
55         }
56         printf("
");
57     }
58 
59 }
60 
61 //取栈顶元素
62 int SatckTop(LinkSatck top)
63 {
64     if (top->next == NULL)
65         printf("栈空
");
66     else
67         return top->next->data;
68 }
69 //求栈长
70 int StackLength(LinkSatck top)
71 {
72     int len = 0;
73     while (top->next != NULL)
74     {
75         len++;
76         top = top->next;
77     }
78 
79     return len;
80 }
81 //初始化栈
82 void Stacks(LinkSatck top)
83 {
84     top->next = NULL;
85 }
86 
87 int main()
88 {
89     LinkSatck top = (LinkSatck)malloc(sizeof(LinkSatck));    //注意    
90     //入栈操作
91     Stacks(top);
92     Push(top, 1);    //入栈
93     Push(top, 2);
94     Push(top, 5);
95     print(top);    //打印栈
96     printf("%3d
", SatckTop(top)); //取栈顶元素
97     printf("%3d
", StackLength(top)); //求栈长
98     return 0;
99 }

View Code

1.2.2 java版

　　代码：

package com.test;

/**
 * 定义节点
 * @author Administrator
 */
public class LinkNode<T> {
    private T data;  //数据
    private LinkNode<T> next; //指针
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public LinkNode<T> getNext() {
        return next;
    }
    public void setNext(LinkNode<T> next) {
        this.next = next;
    }
    public LinkNode(){
        this.data = null;
        this.next = null;
    }
    public LinkNode(T data){
        //super();
        this.data = data;
        this.next = null;
    }
    
}

View Code

package com.test;

public class SqStack<T> {
    // 栈顶节点
    LinkNode<T> top = new LinkNode<T>();

    // 初始化站顶节点
    public void initNode() {
        this.top = new LinkNode<T>();
    }

    // 初始化栈
    public SqStack() {
        this.top.setData(null);
        this.top.setNext(null);
    }

    // 1.判栈空
    public boolean isNull() {
        if (this.top.getNext() == null) {
            return true;
        } else {
            return false;
        }
    }

    // 3.入栈
    public void push(LinkNode<T> node) {
        if(isNull()){
            top.setNext(node);
        }else{
            node.setNext(top.getNext());
            top.setNext(node);
        }
    }

    // 4.出栈
    public T Pop() {
        if (isNull()) {
            return null;
        } else {
           T value = top.getNext().getData();
           top.setNext(top.getNext().getNext());
           return value;
        }
    }

}

View Code

package com.test;

public class TestStack {
    public static void main(String[] args) {
       SqStack<Integer> s = new SqStack<Integer>();
       System.out.println(s.isNull());
       s.push(new LinkNode<Integer>(1));
       s.push(new LinkNode<Integer>(2));
       s.push(new LinkNode<Integer>(3));
       s.push(new LinkNode<Integer>(4));
       s.push(new LinkNode<Integer>(5));
       s.push(new LinkNode<Integer>(6));
       System.out.println(s.Pop());
       System.out.println(s.Pop());
       System.out.println(s.Pop());
       System.out.println(s.Pop());
       System.out.println(s.Pop());
       System.out.println(s.Pop());
    }
}

View Code

　　运行结果：

true
6
5
4
3
2
1

2.串

2.1.定长顺序串

　　串(String)是由零个或多个字符组成的有限序列，又称字符串。

　　(1)长度：串中字符的个数，称为串的长度。
　　(2)空串：长度为零的字符串称为空串。
　　(3)空格串：由一个或多个连续空格组成的串称为空格串。
　　(4)串相等：两个串相等，是指两个串的长度相等且对应的字符都相等。
　　(5)子串：包含在其他串中，这个串称为其他串的子串。
　　(6)主串–包含子串的串，称为子串的主串。
　　(7)模式匹配–子串的定位运算又称为模式匹配，是一个求子串的对一给字符在主串中序号的运算。被匹配的主串称为目标

1.从串s中删除所有与T相同的子串，并返回删除次数

 1 int Delete_SubString(String S,String T)
 2 {
 3     int i=1,n=0;
 4     while(i<StrLength(S)-StrLength(T)+1) 
 5     {
 6         SubString(V,S,i,String(T));//截取串S中从第i个开始，长度为String(T)的子串赋给串V
 7         if(StrCompare(V,T)==0)   //子串和T相等，则删除子串
 8         {
 9           SubString(head,S,1,i-1);  //截取串S中前i-1个字符形成的字符串放在head中
10           //截取串S中串T之后的字符形成的串赋给tail
11           SubString(tail,S,i+StrString(T),StrString(S-i-StrString(T)+1));
12           StrCat(head,tail);//将串tail连接到head后面
13           StrAssign(S,head;);//将删除后的串T后的串重新赋给S
14           n++;
15         }
16         else i++;
17     }
18     return n;   //返回删除的次数
19 }

2.定义定长顺序串

1 #define MAXSIZE  20
2 typedef struct 
3 {
4     char ch[MAXSIZE];
5     int len;
6 }SString;

3.定长顺序串的插入操作

　　在进行串的插入时，插入位置pos将串分为两部分A和B（A的长度为LA，B的长度为LB），待插入的串为T（长度为LT），则有三种不同的情况：

（1）插入后串长小于等于MAXSIZE，则将B后移LT个元素位置，再将LT插入。

（2）插入后串长大于MAXSIZE，且pos+LT<=MAXSIZE;则将B后移时会有部分字符被舍弃。

　（3）插入后串长大于MAXSIZE，且pos+LT>MAXSIZE；则B的全部被舍弃。

　　c语言代码：

 1 int SStrInsert(SString *S, int pos, const SString T)
 2 {
 3     int i;
 4     if (NULL == S || NULL == S->ch || NULL == T.ch || pos<1 || pos>S->len + 1)
 5         return 0;
 6     if (S->len + T.len <= MAXSIZE)
 7     {
 8         for (i = S->len + T.len; i >= pos + T.len; i--)
 9             S->ch[i] = S->ch[i - T.len];
10         for (i = pos; i < pos + T.len; i++)
11             S->ch[i] = T.ch[i - -pos+1];
12         S->len = S->len + T.len;
13 
14     }
15     else if (pos + T.len <= MAXSIZE)
16     {
17         for (i = MAXSIZE; i >= pos + T.len; i--)
18             S->ch[i] = S->ch[i-T.len];
19         for (i = pos; i < pos + T.len; i++)
20             S->ch[i] = T.ch[i - pos + 1];
21         S->len = MAXSIZE;
22     }
23     else
24     {
25         for (i = pos; i <= MAXSIZE; i++)
26           S->ch[i] = T.ch[i - pos + 1];
27           S->len = MAXSIZE; 
28     }
29     return 1;
30 }

View Code

4.串删除函数

　　C语言代码：

 1 int SStrDelete(SString * S, int pos, int len)
 2 {
 3     int i = 1;
 4     if (NULL == S || NULL == S->ch || len < 0 || pos<1 || pos>S->len - len + 1)
 5         return 0;
 6     for (i = pos; i < S->len - len; i++)
 7         S->ch[i] = S->ch[i+len];
 8     S->len = S->len - len;
 9     return 1;
10 }

5.串链接函数

　　在进行串的连接时，假设原始串为S,长度为LS，待连接串为T，长度为LT。则有三种情况：

　　（1）连接后串长小于等于MAXSIZE：直接将B连接在后面；

　　（2）连接后串长大于MAXSZI且LA <MAXSIZE ;则B会有部分字符被舍弃。

　　（3）连接后串长大于MAXSIZE且LA=MAXSIZE:则B的全部被舍弃。

　　C语言代码：

 1 int SStrCat(SString *S, const SString T)
 2 {
 3     int i = 1;
 4     if (NULL == S||NULL == S->ch||NULL == T.ch)
 5     if (S->len + T.len <= MAXSIZE)
 6     {
 7         for (i = S->len + 1; i <= S->len + T.len; i++)
 8             S->ch[i] = T.ch[i-S->len];
 9         S->len = S->len + T.len;
10         return 1;
11     }
12     else if (S->len <= MAXSIZE)
13     {
14         for (i = S->len + 1; i < MAXSIZE; i++)
15             S->ch[i] = T.ch[i-S->len];
16         S->len = MAXSIZE;
17         return 0;
18     }
19     else return 0;
20 }

6.求子串函数

　　C语言代码：

 1 int SubSString(SString *T, SString S, int pos, int len)
 2 {
 3     int i;
 4     if (NULL == T || NULL == T->ch || NULL == S.ch || len<0 || len>S.len - pos + 1 || pos<1 || pos>S.len)
 5         return 0;
 6     for (i = 1; i < len; i++)
 7         T->ch[i] = S.ch[pos + i - 1];
 8     T->len = len;
 9     return 1;
10 }

2.2 串的模式匹配算法

　　串的模式匹配也称为子串的定位操作，即查找子串在主串中出现的位置。设有主串S和子串T，如果在主串S中找到一个与子串T相相等的串，则返回串T的第一个字符在串S中的位置。其中，主串S又称为目标串，子串T又称为模式串。

1.BF模式匹配算法：

　　BF算法思想是从主串S=“s0s1…sn−1”S=“s0s1…sn−1”的第pos个字符开始与模式串T=“t0t1…tm−1”T=“t0t1…tm−1”的第一个字符比较，如果相等则继续逐个比较后续字符；否则从主串的下一个字符开始重新与模式串T的第一个字符比较，依此类推。如果在主串S中存在与模式串T相等的连续字符序列，则匹配成功，函数返回模式串T中第一个字符在主串中S中的位置；否则函数返回-1表示匹配失败。

 1 int Index(SString S, int pos, SString T)
 2 {
 3     int i = pos, j = 1;
 4     while (i < S.len&&j < T.len)
 5     {
 6         if (S.ch[j] == T.ch[j])
 7         {
 8             i++;
 9             j++;
10         }
11         else
12         {
13             i = i - j + 2;
14             j = 1;
15         }
16     }
17     if (j > T.len) return i - T.len;
18     else return 0;
19 }

2.KMP算法

 1 int Index_KMP(SString S,int pos,SString T)
 2 {
 3     int i = pos, j = 1;
 4     while (i <= S.len&&j <= T.len)
 5     {
 6         if (j == 0 || S.ch[i] == T.ch[j])
 7         {
 8             ++i;
 9             ++j;
10         }
11         else j = next[j];
12     }
13     if (j > T.len) return i - T.len;
14     else return 0;
15 }

3.next算法

 1 void Get_Next(SString T, int next[])
 2 {
 3     int j = 1, k = 0;
 4     next[1] = 0;
 5     while (j < T.len)
 6     {
 7         if (k == 0 || T.ch[j] == T.ch[k])
 8         {
 9             ++j;
10             ++k;
11             next[j] = k;
12         }
13         else k = next[k];
14     }
15 }

4.nextval算法

 1 void Get_NextVal(SString T, int next[], int nextval[])
 2 {
 3     int j = 1, k = 0;
 4     Get_Next(T,next);  //获得next的值
 5     nextval[1] = 0;
 6     while (j < T.len)
 7     {
 8         k = next[j];
 9         if (T.ch[j] == T.ch[k])
10             nextval[j] = nextval[k];
11         else
12             nextval[j] = next[j];
13         j++;
14     }
15 }

3.队列

3.1.循环队列

1.循环队列的定义

1 typedef struct
2 {
3     Decltype data[MAXSIZE];
4      int front, rear;
5  }CSeQueue;

2.置队空

1 CSeQueue * InitCSeQueue()
2 {
3     CSeQueue *q;
4     q = (CSeQueue*)malloc(sizeof(CSeQueue));
5     q->front = q->rear = MAXSIZE - 1;
6     return q;
7 }

3.入队

 1 int InSeQueue(CSeQueue *q, Decltype x)
 2 {
 3     if ((q->rear + 1) % MAXSIZE == q->front)
 4     {
 5         printf("队满");
 6         return false;
 7     }
 8     else
 9     {
10         q->rear = (q->rear + 1) % MAXSIZE;//入队时队尾指针
11         q->data[q->rear] = x;
12         return true;
13     }
14 }

4.出队

 1 int OutSeQueue(CSeQueue *q, Decltype *x)
 2 {
 3     if (q->front == q->rear)
 4     {
 5         printf("空队");
 6         return false;
 7     }
 8     else
 9     {
10         q->front = (q->front + 1) % MAXSIZE;//出队时队头指针
11         *x = q->data[q->front]; //读出队头元素
12         return true;
13     }
14 }

5.判队空

1 int EmptySeQueue(CSeQueue *q)
2 {
3     if (q->front == q->rear)
4         return true;
5     else
6         return false;
7 }

3.2.链队列

1.链队列数据类型描述

 1 typedef struct node
 2 {
 3     Decltype data;
 4     struct node *next;
 5 }QNode;//列队结点的类型
 6 typedef struct
 7 {
 8     QNode *front;
 9     QNode *rear;
10 }LQueue;//将头尾指针封装在一起的链队
11 LQueue *q //定义指向列队的指针

2.创建一个带头结点的空队

1 LQueue *init_LQueue()
2 {
3     LQueue *q, *p;
4     q = malloc(sizeof(LQueue));//申请头尾指针结点
5     p = malloc(sizeof(QNode));//申请链队头结点
6     p->next = NULL;
7     q->front = q->rear = p;
8     return q;
9 }

3.入队

1 void InitQueue(LQueue *q, Decltype x)
2 {
3     QNode *p;
4     p = malloc(sizeof(QNode));//申请新结点
5     p->data = x;
6     p->next = NULL;
7     q->rear->next = p;
8     q->rear = p;
9 }

4.判队空

1 int Empty_LQueue(LQueue *q)
2 {
3     if (q->front == q->rear)
4         return 0;
5     else return true;
6 }

5.出队

int Out_LQueue(LQueue *q, Decltype x)
{
    QNode *p;
    if (Empty_LQueue(q))
    {
        printf("队空");
        return false;
    }
    else
    {
        p = q->front->next;
        q->front->next = p->next;
        *x = p->data; 
        free(p);
        if (q->front->next == NULL)
            q->rear = q->front;
        //只有一个元素时，出队后队空，修改队尾指针
        return true;
    }
}

4.单链表

4.1.特点

（1）在单链表上插入，删除一个节点，必须知道其节点的前驱节点。

（2）单链表不具有按序号随机访问的特点，只能从头指针开始依次进行访问

（3）链表上实现的插入和删除运算不用移动节点，仅需修改指针。

4.2.操作

1.单链表节点的定义

1 //单链表节点的定义
2 typedef int ElemType;
3 typedef struct node
4 {
5     ElemType  data;
6     struct node *next;
7 }Lnode,*LinkList;

2.头插法建立单链表

　　思想：首先申请一个头结点，并且将头结点指针置空，然后每读入一个数据元素则申请一个结点，并插在链表的头结点之后。时间复杂度为O(n)。

 1 //单链表的头插法
 2 LinkList Creat_LinkList()
 3 {
 4     int x;
 5     Lnode *s;
 6     LinkList H = (LinkList)malloc(sizeof(Lnode)); //生成头结点
 7     H->next = NULL;
 8     scanf_s("%d", &x);
 9     while (x != -1)
10     {
11         s = (LinkList)malloc(sizeof(Lnode));
12         s->data = x;
13         s->next = H->next;
14         H->next = s;
15         scanf_s("%d",&x);
16     }
17     return H;
18 }

3.尾插法建立单链表

　　思想：首先申请一个头结点，并且将头结点指针置空，头指针H和为指针r都指向头结点，然后按照线性表中元素的顺序依次读入数据，如果不是结束标志，则申请结点，将心结点插入r所指结点的后面，并使r指向新节点。时间复杂度为O(n)。

 1 //单链表的尾插法
 2 LinkList Creat_LinkList()
 3 {
 4     int x;
 5     LinkList H = (LinkList)malloc(sizeof(Lnode)); //生成头结点
 6     Lnode *s, *r = H;
 7     H->next = NULL;
 8     scanf_s("%d", &x);
 9     while (x != -1)
10     {
11         s = (LinkList)malloc(sizeof(Lnode));
12         s->data = x;
13         H->next = s;
14         s->next = NULL;
15         r = s;
16         scanf_s("%d", &x);
17     }
18     return H;
19 }

4.求单链表的长

　　时间复杂度为O(n)。

 1 //求表长
 2 int Length_LInkList(LinkList  H)
 3 {
 4     Lnode *p = H;//指向头结点的指针变量p
 5     int j = 0;
 6     while (p->next != NULL)
 7     {
 8         p = p->next;
 9         j++;
10     }
11     return j;
12 }

5.查找特定序号的节点的指针

　　时间复杂度为O(n)。

//查找给定节点的指针
LinkList Get_LinkList(LinkList H, int k)
{
    LNode *p = H;
    int j = 0;
    while (p->next != NULL && j < k)
    {
        p = p->next;
        j++;
    }
    if (j == k)
        return p;
    else
        return NULL;
}

6.查找特定值所在的位置时间复杂度为O(n)。

1 Lnode *Locate_LinkList(LinkList H, ElemType x)
2 {
3     Lnode *p = H->next;
4     while (p != NULL && p->data != x)
5     {
6         p = p->next;
7         return p;
8     }
9 }

7.单链表的插入

　　时间复杂度为O(n)。

 1 int Insert_LinkList(LinkList H,int i,ElemType x)
 2 {
 3     Lnode *p, *s;
 4     p = Get_LinkList(H, i - 1);//查找第一个节点
 5     if (p == NULL)
 6     {
 7         printf("插入位置错误。");
 8         return false;
 9     }
10     else
11     {
12         s = (LinkList)malloc(sizeof(Lnode));
13         s->data = x;
14         s->next = p->next;
15         p->next = s;
16         return true;
17     }
18         
19 }

8.删除节点

　　时间复杂度为O(n)。

 1 //p指向要删除的节点，q是p的前驱节点
 2 int Del_linkList(LinkList H, int i)
 3 {
 4     LinkList p, q;
 5     p = Get_LinkList(H, i - 1);//查找第i-1个节点
 6     if (p == NULL)
 7     {
 8         printf("第i-1个节点不存在。");
 9         return false;
10     }
11     else
12     {
13         if (p->next == NULL)
14         {
15             printf("第i-1个节点不存在。");
16             return false;
17         }
18         else
19         {
20             q = p->next;
21             p->next = q->next;
22             free(q);
23             return true;
24         }
25     }
26 }

9.单链表的倒置

　　时间复杂度为O(n)

 1 void Reverse(LinkList H)
 2 {
 3     Lnode *p,*q;
 4     p = H->next;
 5     H->next = NULL;
 6     while (p)
 7     {
 8         q = p;
 9         p = p->next;
10         q->next = H->next;
11         H->next = q;
12     }
13 }

10.单链表删除重复节点

　　时间复杂度为O(n^2)。

 1 void pur_LinkList(LinkList H)
 2 {
 3     Lnode *p, *q, *r;
 4     p = H->next;
 5     if (p!=NULL)
 6     while (p->next)
 7     { 
 8         q = p;
 9         while (q->next)
10         {
11             if (q->next->data == p->data){
12                 r = q->next;
13                 q->next = r->next;
14                 free(q);
15             }
16             else 
17             {
18                 q = q->next;
19             }
20         }
21         p = p->next;
22     }
23 }

11.两个单链表的差

 1 void Difference(LinkList LA, LinkList LB)
 2 {
 3     Lnode *pre,*q, *p, *r;
 4     pre = LA;
 5     p = LA->next;
 6     while (p != NULL)
 7     {
 8         q = LB->next;
 9         while (q != NULL&&q->data != p->data) q = q->data;
10         if (q != NULL)
11         {
12             r = p;
13             pre->next = p->next;
14             p = p->next;
15             free(r);
16         }
17         else
18         {
19             pre = p;
20             p=p->next;
21         }
22     }
23 }

View Code

12.部分方法综合测试

  1 #include <stdio.h>
  2 #include "malloc.h"
  3 typedef struct node
  4 {
  5     int val;     //数据域
  6     struct node *next; //指针域
  7 }LNode,*LinkList;
  8 
  9 //头插法建立单链表
 10 LinkList Creat_LinkList()
 11 {
 12     LinkList H = (LinkList)malloc(sizeof(LNode));
 13     H->next = NULL;
 14     LNode *s;
 15     int x;
 16     scanf_s("%d",&x);
 17     while (x != -1)
 18     {
 19         s = (LinkList)malloc(sizeof(LNode));
 20         s->val = x;
 21         s->next = H->next;
 22         H->next = s;
 23         scanf_s("%d", &x);
 24     }
 25     return H;
 26 }
 27 
 28 //单链表的尾插法
 29 LinkList Creat_LinkListEnd()
 30 {
 31     int x;
 32     LinkList H =(LinkList) malloc(sizeof(LNode));
 33     H->next = NULL;
 34     LNode *s,*r=H;
 35     scanf_s("%d",&x);
 36     while (x != -1)
 37     {
 38         s = (LinkList)malloc(sizeof(LNode));
 39         s->val = x;
 40         s->next = r->next;
 41         r->next = s;
 42         r = s;
 43         scanf_s("%d",&x);
 44     }
 45     return H;
 46 }
 47 
 48 //求表长
 49 int length_LinkList(LinkList H)
 50 {
 51     LNode *p = H;
 52     int j = 0;
 53     while (p->next!=NULL)
 54     {
 55         p = p->next;
 56         j++;
 57     }
 58     return j;
 59 }
 60 //查找给定节点的指针
 61 LinkList Get_LinkList(LinkList H, int k)
 62 {
 63     LNode *p = H;
 64     int j = 0;
 65     while (p->next != NULL && j < k)
 66     {
 67         p = p->next;
 68         j++;
 69     }
 70     if (j == k)
 71         return p;
 72     else
 73         return NULL;
 74 }
 75 //删除给点节点的值
 76 //p指向要删除的节点，q是p的前驱节点
 77 int Del_linkList(LinkList H, int i)
 78 {
 79     LinkList p, q;
 80     p = Get_LinkList(H, i - 1);//查找第i-1个节点
 81     if (p == NULL)
 82     {
 83         printf("第i-1个节点不存在。");
 84         return false;
 85     }
 86     else
 87     {
 88         if (p->next == NULL)
 89         {
 90             printf("第i-1个节点不存在。");
 91             return false;
 92         }
 93         else
 94         {
 95             q = p->next;
 96             p->next = q->next;
 97             free(q);
 98             return true;
 99         }
100     }
101 }
102 
103 //打印单链表
104 void print(LinkList head)
105 {
106     LinkList p = head->next;
107     while(p)
108     {
109         printf("%3d",p->val);
110         p = p->next;
111     }
112     printf("
");
113 }
114 int main()
115 {
116     LinkList head = NULL;
117     
118     //头插法创建
119     //head = Creat_LinkList();    
120     //print(head);
121 
122     //尾插法创建
123     //head = Creat_LinkListEnd();
124     //print(head);
125 
126     //求表长
127     //head = Creat_LinkListEnd();
128     //printf("%d
", length_LinkList(head));
129     //print(head);
130 
131     //删除位置为5的结点
132     head = Creat_LinkListEnd();
133     Del_linkList(head,5);
134     print(head);
135 
136     return 0;
137 }

View Code

5.静态链表，动态链表

5.1.静态链表

　　含义：链表中所有的节点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表成为静态链表。

　　举一个简单的例子如下：

 1 #include<stdio.h>
 2 struct MyStruct
 3 {
 4     int num;
 5     float score;
 6     struct MyStruct *netx;
 7 };
 8 int main()
 9 {
10     struct MyStruct a, b, c, *p, *head;
11     a.num = 1; a.score = 89;
12     b.num = 1; b.score = 86;
13     c.num = 1; c.score = 87;
14     head = &a;
15     a.netx = &b;
16     b.netx = &c;
17     c.netx = NULL;
18     //p = &a;
19     while (head != NULL)
20     {
21         printf("%d, %5.1f
", head->num, head->score);
22         head = head->netx;
23     }
24     return 0;
25 }

5.2.动态链表

　　含义：建立动态链表是指在程序执行过程中从无到有的建立一个链表，即一个一个地开辟节点和输入各节点数据，并建立起前后相连的关系；

　　举例如下：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define LEN sizeof(struct MyStruct)
 4 struct MyStruct
 5 {
 6     long num;
 7     float score;
 8     struct MyStruct *netx;
 9 };
10 int n;
11 struct MyStruct *creat()
12 {
13     struct  MyStruct *head;
14     struct  MyStruct *p1, *p2;
15     n = 0;
16     p1 = p2 = (struct MyStruct*)malloc(LEN);
17     scanf_s("%d,%f", &p1->num, &p1->score);
18     head = NULL;
19     while (p1->num != 0)
20     {
21         n = n + 1;
22         if (n == 1)head = p1;
23         else p2->netx = p1;
24         //p2 = p1;
25         p1 = (struct MyStruct*)malloc(LEN);
26         scanf_s("%d,%f", &p1->num, &p1->score);
27     }
28     p2->netx = NULL;
29     return (head);
30 }
31 int main()
32 {
33     struct MyStruct *pt;
34     pt = creat();
35     printf("%d,%5.1f
", pt->num, pt->score);
36     return 0;
37 }

　　程序分析：程序中的malloc（LEN）的作用就是开辟一个长度为LEN的内存，LEN已经定义为sizeof（struct Mystruct）结构体。

6.线性表的顺序存储

　　特点：在内存中用一块地址连续的存储空间按顺序存储线性表的各个数据元素，逻辑上相邻的两个元素在物理结构上也是相邻的。存储密度高，且能随机的存储数据元素，但进行插入，删除时需要移动大量的数据元素，而且顺序表需要预先分配存储空间，若表长n的值变化较大，则存储规模事先难以预料。

1.线性表的顺序存储结构描述

1 #define MAXSIZE 10     //线性表的最大长度
2 typedef int ElemType;
3 typedef struct
4 {
5     ElemType elem[MAXSIZE];
6     int length;
7 }seqList;

2.顺序表的定义

seqList *L;

　　下标的取值范围为 1<= i<=MAXSIZE;

3.顺序表的初始化

//顺序表的初始化
void init_SeqList(seqList *L)
{
     L->length = 0;       
}

　　调用方法为 init_SeqList(&L);

4.顺序表的插入

//顺序表的插入
int Insert_SeqList(seqList *L, int i, ElemType x)
{
    int j;
    if (L->length == MAXSIZE - 1)
    {
        printf("表满
");
        return -1;
    }
    if (i<0 || i>L->length)
    {
        printf("位置错误
");
        return false;
    }
    for (j = L->length; j >= i; j++)
        L->elem[j + 1] = L->elem[j];
    L->elem[i] = x;
    L->length = L->length + 1;
    return true;
}

　　操作步骤：

（1）将an~ai按从后向前的顺序下载移动，为新元素让出位置

（2）将x置入空出的第 i 个位置

（3）修改表长

　　插入的时间复杂度分析：顺序插入的时间主要消耗在数据元素的移动上，有n+1个位置可以插入，在等概率的情况下做顺序表插入运算须移动一半的数据元素，故时间复杂度是O(n)

5.顺序表的删除

//顺序表的删除
int Delete_SeqList(seqList *L, int i)
{
    int j;
    if (i<0 || i>L->length)
    {
        printf("不存在第i个元素");
        return false;
    }
    for (j = i; j <= L->length-1; j++)
        L->elem[j] = L->elem[j + 1];
    L->length--;
    return true;
}

　　操作步骤：

　　（1）将ai+1~an依次向上移动；

　　（2）将length的值减一

　　时间复杂度也是O(n)。

6.顺序表的按值查找

1 //顺序表中按值查找
2 int Location_SeqList(seqList *L,ElemType x)
3 {
4     int i =1;
5     while (i <= L->length && L->elem[i] != x)
6         i++;
7     if (i > L->length) return false;
8     else return i;     //返回x的存储位置
9 }

　　时间复杂度分析：当a1 == x时，只比较一次，当an == x，平均比较次数为（n+1）/2，所以时间复杂度也是O（n）。

7.将两个从小到大排列的顺序表合并成一个从小到大排列的顺序表

 1 //两个顺序表的合并
 2 void mergr(seqList *A, seqList *B, seqList *C)
 3 {
 4     int i = 1, j = 1, k = 1;
 5     while (i <= A->length &&j <= B->length)
 6     if (A->elem[i] < B->elem[j])
 7         C->elem[k++] = A->elem[i++];
 8     else
 9         C->elem[k++] = B->elem[j++];
10     while (i <= A->length)
11         C->elem[k++] = A->elem[i++];
12     while (i <= B->length)
13         C->elem[k++] = B->elem[j++];
14     C->length = A->length + B->length;
15 }

　　时间复杂度是O(n+m),m和n分别是两个表的长度