链表的简单操作

今天晚上又重新温故了链表的简单操作

1关于链表的定义在此不多赘述，该文件为link.h文件

#define ElemType char


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

初始化

#include <stdio.h>
#include "link.h"

// init
void InitList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
}

int main(int argc, char const *argv[])
{
    Node *p = NULL;
    InitList(&p);
    return 0;
}

在初始化时候，为什么形参是一个二级指针呢？

看主函数，我们明白p所指向的事一个头结点，头结点的下一个结点才是第一个元素结点，这也是为什么p为二级指针的原因

2接下来是链表的插入，输入若干个字符以‘$’为结束符

// 用头插法创建链表

void CreatFromHead(LinkList L)
{
    Node *s;
    char c;
    int flag = 1;
    while(flag)
    {
        c = getchar();
        if(c != '$')
        {
            s = (LinkList)malloc(sizeof(Node));
            s->data = c;
            s->next = L->next;
            L->next = s;
        }
        else
        {
            flag = 0;
        }
    }
}

void CreatFromTail(Node *L)
{
    Node *r, *s;
    char c;
    int flag = 1;
    r = L;
    while(flag)
    {
        c = getchar();
        if(c != '$')
        {
            s = (LinkList)malloc(sizeof(Node));
            s->data = c;
            r->next = s;
            r = s;
        }
        else
        {
            flag = 0;
            r->next = NULL;
        }
    }
}

输入1234，对应头插法的结果是4321，对应尾插法的结果是1234

3链表的打印

void print(Node *L)
{
    Node *t, *p = L;
    t = p->next;                //t是头结点
    while(t != NULL)
    {
        printf("%c", t->data);
        t = t->next;
    }
}

因为链表的第一个元素是第二个结点，因此我们定义了t变量

4查出第链表中第i个元素

Node* Get(Node *L, int i)
{
    Node *p;
    int j = 0;
    if(i < 0)
        return NULL;
    p = L;
    
    for(j = 0; j < i && p->next != NULL; j++)
    {
        p = p->next;
    }
    if(j == i)
        return p;
    else
        return NULL;
}

也比较简单，在遍历的时候考虑，有没有结束和是否到了i这个位置两个因素即可。

下面是所有的代码

 1 #include <stdio.h>
 2 #include "link.h"
 3 
 4 // init
 5 void InitList(LinkList *L)
 6 {
 7     *L = (LinkList)malloc(sizeof(Node));
 8     (*L)->next = NULL;
 9 }
10 
11 // 用头插法创建链表
12 
13 void CreatFromHead(LinkList L)
14 {
15     Node *s;
16     char c;
17     int flag = 1;
18     while(flag)
19     {
20         c = getchar();
21         if(c != '$')
22         {
23             s = (LinkList)malloc(sizeof(Node));
24             s->data = c;
25             s->next = L->next;
26             L->next = s;
27         }
28         else
29         {
30             flag = 0;
31         }
32     }
33 }
34 
35 void CreatFromTail(Node *L)
36 {
37     Node *r, *s;
38     char c;
39     int flag = 1;
40     r = L;
41     while(flag)
42     {
43         c = getchar();
44         if(c != '$')
45         {
46             s = (LinkList)malloc(sizeof(Node));
47             s->data = c;
48             r->next = s;
49             r = s;
50         }
51         else
52         {
53             flag = 0;
54             r->next = NULL;
55         }
56     }
57 }
58 
59 
60 void print(Node *L)
61 {
62     Node *t, *p = L;
63     t = p->next;                //t是头结点
64     while(t != NULL)
65     {
66         printf("%c", t->data);
67         t = t->next;
68     }
69 }
70 
71 Node* Get(Node *L, int i)
72 {
73     Node *p;
74     int j = 0;
75     if(i < 0)
76         return NULL;
77     p = L;
78     
79     for(j = 0; j < i && p->next != NULL; j++)
80     {
81         p = p->next;
82     }
83     if(j == i)
84         return p;
85     else
86         return NULL;
87 }
88 
89 int main(int argc, char const *argv[])
90 {
91     Node *p = NULL;
92     InitList(&p);
93     CreatFromTail(p);
94     print(p);
95     return 0;
96 }

心得：

哈哈，再一次玩链表是靠自己一点点看书，自己一点点理解起来，说真的当时院长讲链表的时候自己一点也没搞清楚，但是自己花时间琢磨，慢慢的也就理解了