# C 数据结构

**Repository Path**: xie-mingshan/c---data-structure

## Basic Information

- **Project Name**: C 数据结构
- **Description**: C && Python data-structure
- **Primary Language**: Python
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-09-25
- **Last Updated**: 2022-10-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: C语言, Python, 数据结构

## README

#### 1.结构体

##### 1.1 定义结构类型(模具)

- 方式一,直接定义

  - ```c
    struct stu{
    	成员列表;
    };
    struct stu xiao;
    ```

- 方式二,直接定义完结构体**类型**再后定义结构体**变量**

  - ```c
    struct stu{
    	成员列表;
    }xiao;
    ```

- 方式三,无名定义结构**类型**再后定义结构体**变量**,注意由于**无名**所以无法再定义其他结构体变量

  - ```c
    struct{
    	成员列表;
    }xiao;
    ```

- ★ 方式四,定义结构**类型**,同给该类型名起别名,struct stu <=> Stu

  - ```c
    //无名变有名也适用
    typedef struct stu{
    	成员列表;
    }Stu;
    ```

##### 1.2 结构体变量

- 定义结构体变量
  - Stu xiao;
- 定义结构体指针变量
  - Stu *p = &xiao;
- 取结构体变量成员值
  - xiao.age <=> *p.age <=> p->age 

##### 1.3 结构体变量赋值

- 相同类型的结构体变量可以相互赋值

##### 1.4 结构体变量指针

- 结构体变量指针类型与结构体类型一致

#### 2.线性表

##### 2.1 顺序表-C

![image-20220926114357485](https://gitee.com/xie-mingshan/c---data-structure/raw/shan/0.0.1/%E5%B1%95%E7%A4%BA%E5%9B%BE/%E9%A1%BA%E5%BA%8F%E8%A1%A8.png)

- 创建

  - ```c
    //创建线性表
    void create(Sqlist *p)
    {
        //存储用户输入的线性表长度
        int create_len;
        printf("您要输入多少个顺序表元素：");
        scanf("%d",&create_len);
        p->length = create_len;
    
        //存储线性表的长度
        for(int i=0;i<create_len;i++)
        {
            printf("请输入第%d个元素(Enter)",i+1);
            scanf("%d",&(p->ele[i]));
        }
    }
    ```

- 插入

  - ```c
    //★增加元素
    void insert(Sqlist *p)
    {
        //:param    position:插入元素位置(非数组下标)
        //:param    ele:插入元素
        int position,ele,i;
        printf("请输入插入的位置position及插入的元素ele(空格分隔)");
        scanf("%d%d",&position,&ele);
        //判断是否超过线性表长度或小于等于零
        if(position<=0 || position>p->length)
        {
            printf("插入元素位置越界或超过线性表长度");
        }
        //把插入元素位置的(当前元素及往后元素下标后移)
        for(i=p->length;i>=position;i--)
        {
            p->ele[i] = p->ele[i-1];
        }
        //增加新元素到数组里面
        p->ele[i] = ele;
        //长度自增1
        p->length++;
    }
    ```

- 删除

  - ```c
    //★删除元素
    void deleter(Sqlist *p)
    {
        int position;
        printf("请输入删除元素的位置");
        scanf("%d",&position);
        //判断是否超过线性表长度或小于等于零
        if(position<=0 || position>p->length)
        {
            printf("插入元素位置越界或超过线性表长度");
        }
        //把删除元素位置的(往后元素下标前移)
        for(int i=position;i<p->length;i++)
        {
            p->ele[i-1] = p->ele[i];
        }
        //长度自减1
        p->length--;
    }
    ```

- 查看

  - ```c
    //查看线性表的元素
    void show(Sqlist *p)
    {
        //清屏
        system("cls");
        //获取线性表的长度
        int len = p->length;
        //遍历获取每个元素
        for(int i=0;i<len;i++)
        {
            printf("\n%d\t%d",i+1,p->ele[i]);
        }
    
    }
    ```

- 实现

  - ```c
    #include <stdio.h>
    #include "stdlib.h"
    #define MAXSIZE 100
    
    //别名,元素类型
    typedef int EleType;
    //定义线性表结构体类型
    typedef struct
    {
        EleType ele[MAXSIZE];
        int length;
    
    }Sqlist;
    
    //查看
    void show(Sqlist *p);
    //创建
    void create(Sqlist *p);
    //增加
    void insert(Sqlist *p);
    //删除
    void deleter(Sqlist *p);
    
    
    int main()
    {
        Sqlist lineS;
        int command;
        do
        {
            printf("\n1-创建线性表\t2-增加元素\n");
            printf("\n3-删除元素\t4-退出程序\n");
            printf("请输入您的指令：");
            scanf("%d",&command);
            switch(command)
            {
                case 1:
                    create(&lineS);
                    show(&lineS);
                    break;
                case 2:
                    insert(&lineS);
                    show(&lineS);
                    break;
                case 3:
                    deleter(&lineS);
                    show(&lineS);
                    break;
                case 4:
                    exit(0);
            }
        }while(command<=4);
        return 0;
    }
    
    //查看线性表的元素
    void show(Sqlist *p)
    {
        //清屏
        system("cls");
        //获取线性表的长度
        int len = p->length;
        //遍历获取每个元素
        for(int i=0;i<len;i++)
        {
            printf("\n%d\t%d",i+1,p->ele[i]);
        }
    
    }
    
    //创建线性表
    void create(Sqlist *p)
    {
        //存储用户输入的线性表长度
        int create_len;
        printf("您要输入多少个顺序表元素：");
        scanf("%d",&create_len);
        p->length = create_len;
    
        //存储线性表的长度
        for(int i=0;i<create_len;i++)
        {
            printf("请输入第%d个元素(Enter)",i+1);
            scanf("%d",&(p->ele[i]));
        }
    }
    
    
    //增加元素
    void insert(Sqlist *p)
    {
        //:param    position:插入元素位置(非数组下标)
        //:param    ele:插入元素
        int position,ele,i;
        printf("请输入插入的位置position及插入的元素ele(空格分隔)");
        scanf("%d%d",&position,&ele);
        //判断是否超过线性表长度或小于等于零
        if(position<=0 || position>p->length)
        {
            printf("插入元素位置越界或超过线性表长度");
        }
        //把插入元素位置的(当前元素及往后元素下标后移)
        for(i=p->length;i>=position;i--)
        {
            p->ele[i] = p->ele[i-1];
        }
        //增加新元素到数组里面
        p->ele[i] = ele;
        //长度自增1
        p->length++;
    }
    
    //删除元素
    void deleter(Sqlist *p)
    {
        int position;
        printf("请输入删除元素的位置");
        scanf("%d",&position);
        //判断是否超过线性表长度或小于等于零
        if(position<=0 || position>p->length)
        {
            printf("插入元素位置越界或超过线性表长度");
        }
        //把删除元素位置的(往后元素下标前移)
        for(int i=position;i<p->length;i++)
        {
            p->ele[i-1] = p->ele[i];
        }
        //长度自减1
        p->length--;
    }
    ```

##### 2.2 顺序表-P

- 创建

```python
#初始化顺序表
def __init__(self,maxsize=100):
    #线性表长度
    self.length = 0;
    #构建线性表空间
    self.sql = maxsize*[0]
#构建线性表元素
def create(self):
    num = eval(input("您要输入多少个顺序表元素："))
    for i in range(num):
        data = input("第{}个元素:".format(i+1))
        seq.sql[i] = data
        seq.length += 1
```

- 插入

```python
#插入元素
def insert(self):
    posnum,data = list(map(int,input("请输入您要插入的位置及数据：").split()))
    #判断输入的位置数是否有效
    if posnum>self.length or posnum <= 0:
        return
    #从插入位置数至线性表尾元素全部后移
    else:
        for i in range(self.length,posnum-1,-1):
            self.sql[i] = self.sql[i-1]
        self.sql[posnum-1] = data
        self.length += 1
```

- 删除

```python
#删除元素
def delete(self):
    posnum = eval(input("请输入您要删除的位置："))
    #判断输入的位置数是否有效
    if posnum>self.length or posnum <= 0:
        return
    #从删除位置数至线性表尾元素全部前移
    else:
        for i in range(posnum,self.length):
            self.sql[i-1] = self.sql[i]
        self.length -= 1
```

- 查看

```python
#遍历顺序表
def outline(self):
    print("========线性表元素(已更新)========")
    for i in range(self.length):
        print(self.sql[i])
```

- 实现

```python
#顺序表类
class SeqList:
    #初始化顺序表
    def __init__(self,maxsize=100):
        #线性表长度
        self.length = 0;
        #构建线性表空间
        self.sql = maxsize*[0]
    #构建线性表元素
    def create(self):
        num = eval(input("您要输入多少个顺序表元素："))
        for i in range(num):
            data = input("第{}个元素:".format(i+1))
            seq.sql[i] = data
            seq.length += 1
    #插入元素
    def insert(self):
        posnum,data = list(map(int,input("请输入您要插入的位置及数据：").split()))
        #判断输入的位置数是否有效
        if posnum>self.length or posnum <= 0:
            return
        #从插入位置数至线性表尾元素全部后移
        else:
            for i in range(self.length,posnum-1,-1):
                self.sql[i] = self.sql[i-1]
            self.sql[posnum-1] = data
            self.length += 1
    #删除元素
    def delete(self):
        posnum = eval(input("请输入您要删除的位置："))
        #判断输入的位置数是否有效
        if posnum>self.length or posnum <= 0:
            return
        #从删除位置数至线性表尾元素全部前移
        else:
            for i in range(posnum,self.length):
                self.sql[i-1] = self.sql[i]
            self.length -= 1
    #遍历顺序表
    def outline(self):
        print("========线性表元素(已更新)========")
        for i in range(self.length):
            print(self.sql[i])
    
if __name__ == "__main__":
    seq = SeqList()
    while 1:
        print("""
              1-创建顺序表      2-插入元素
              3-删除元素        4-退出程序
          """)
        command = eval(input("请输入您的指令："))
        #创建线性表
        if(command==1):        
            seq.create()
            seq.outline()
        #增加元素
        elif(command==2):
             seq.insert()
             seq.outline()
        #删除元素
        elif(command==3):
            seq.delete()
            seq.outline()
        else:
            break
```



##### 2.3 单链表-C

![image-20220926114357485](https://gitee.com/xie-mingshan/c---data-structure/raw/master/%E5%B1%95%E7%A4%BA%E5%9B%BE/%E5%8D%95%E9%93%BE%E8%A1%A8.png)

- 创建

```c
/*
    funcdesc创建单链表
    parse:None
*/
Node* createSlist()
{
    //创建头结点
    Node *HeadNode = (Node*)malloc(sizeof(Node));
    HeadNode->next = NULL;
    return HeadNode;
}
```

- 插入

```c
/*
    funcdesc: 插入结点到单链表
    parse: Node* HeadNod,头结点指针;
    parse: data,插入的数据域
*/
void insertNode(Node* HeadNode)
{
    int data;
    printf("请输入新结点数据域:");
    scanf("%d",&data);

    //创建新结点
    Node *NewNode = (Node*)malloc(sizeof(Node));
    //构建新结点数据域
    NewNode->data = data;
    //构建新结点指针域
    NewNode->next = HeadNode->next;
    //头结点指向新结点地址
    HeadNode->next = NewNode;

}
```

- 查看

```c
/*
    funcdesc: 遍历单链表结点
    parse: Node* HeadNod,头结点指针;
*/
void outline(Node* HeadNode)
{
    //获取第一个结点
    Node *curNode = HeadNode->next;
    if(curNode==NULL)
    {
        printf("该单链表目前为空\n");
        return;
    }
    while(curNode)
    {
        printf("%d\n",curNode->data);
        curNode = curNode->next;
    }

}
```

- 删除

```c
/*
    funcdesc: 删除单链表某结点
    parse: Node* HeadNod,头结点指针;
*/
void deleteNode(Node *HeadNode)
{
    int num,count=0;
    printf("您想删除第几个结点:");
    scanf("%d",&num);

    //前驱结点
    Node *preNode = HeadNode;
    //当前结点
    Node *curNode = HeadNode->next;
    //判断是否为空表
    if(curNode==NULL)
    {
        printf("该单链表目前为空\n");
        return;
    }
    //判断是否为最后一个
    while(curNode)
    {
        count += 1;
        if(num==count)
        {
            //把删除的结点的后驱结点地址,赋值给前驱结点的next
            preNode->next = curNode->next;
            //释放删除结点的内存
            free(curNode);
            break;
        }
        else
        {
            preNode = curNode;
            curNode = curNode->next;
        }
        if(!curNode) printf("删除失败,请输入有效结点位置!\n");
    }
}
```

- 实现

```c
/*单链表实现*/
#include <stdio.h>
#include <stdlib.h>

//定义数据域类型
typedef int DataType;
//结点(结构体)
typedef struct node
{
    //数据域
    DataType data;
    //指针域
    struct node *next;
}Node;


//单链表函数功能模块
Node* createSlist();
void insertNode(Node* HeadNode);
void outline(Node* HeadNode);
void deleteNode(Node *HeadNode);

int main()
{
    int command=0;
    Node *HeadNode;
    while(command!=4)
    {
        printf("\n1-创建单链表     2-插入结点\n");
        printf("\n3-删除结点       4-退出程序\n\n");
        printf("请输入您的操作：");
        scanf("%d",&command);
        switch(command)
            {
            case 1:
                //创建单链表
                HeadNode = createSlist();
                printf("\n=============================\n");
                printf("单链表创建成功,addr:%X",HeadNode);
                printf("\n=============================\n");
                break;
            case 2:
                //插入结点
                insertNode(HeadNode);
                //遍历单链表
                printf("\n===========单链表结点(已更新)=========\n");
                outline(HeadNode);
                break;
            case 3:
                //删除结点
                deleteNode(HeadNode);
                //遍历单链表
                printf("\n===========单链表结点(已更新)=========\n");
                outline(HeadNode);
                break;
            case 4:
                //退出程序
                break;
            }
    }
    return 0;
}


/*
    funcdesc创建单链表
    parse:None
*/
Node* createSlist()
{
    //创建头结点
    Node *HeadNode = (Node*)malloc(sizeof(Node));
    HeadNode->next = NULL;
    return HeadNode;
}


/*
    funcdesc: 插入结点到单链表
    parse: Node* HeadNod,头结点指针;
    parse: data,插入的数据域
*/
void insertNode(Node* HeadNode)
{
    int data;
    printf("请输入新结点数据域:");
    scanf("%d",&data);

    //创建新结点
    Node *NewNode = (Node*)malloc(sizeof(Node));
    //构建新结点数据域
    NewNode->data = data;
    //构建新结点指针域
    NewNode->next = HeadNode->next;
    //头结点指向新结点地址
    HeadNode->next = NewNode;

}

/*
    funcdesc: 遍历单链表结点
    parse: Node* HeadNod,头结点指针;
*/
void outline(Node* HeadNode)
{
    //获取第一个结点
    Node *curNode = HeadNode->next;
    if(curNode==NULL)
    {
        printf("该单链表目前为空\n");
        return;
    }
    while(curNode)
    {
        printf("%d\n",curNode->data);
        curNode = curNode->next;
    }

}

/*
    funcdesc: 删除单链表某结点
    parse: Node* HeadNod,头结点指针;
*/
void deleteNode(Node *HeadNode)
{
    int num,count=0;
    printf("您想删除第几个结点:");
    scanf("%d",&num);

    //前驱结点
    Node *preNode = HeadNode;
    //当前结点
    Node *curNode = HeadNode->next;
    //判断是否为空表
    if(curNode==NULL)
    {
        printf("该单链表目前为空\n");
        return;
    }
    //判断是否为最后一个
    while(curNode)
    {
        count += 1;
        if(num==count)
        {
            //把删除的结点的后驱结点地址,赋值给前驱结点的next
            preNode->next = curNode->next;
            //释放删除结点的内存
            free(curNode);
            break;
        }
        else
        {
            preNode = curNode;
            curNode = curNode->next;
        }
        if(!curNode) printf("删除失败,请输入有效结点位置!\n");
    }
}
```

##### 2.4 单链表-P

- 创建单链表

```python
#创建单链表
def __init__(self):
    self.head = None
```

- 添加元素

```python
#添加元素
def add(self,data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
```

- 插入元素

```python
#插入元素
def insert(self,posele,data):
    if not self.head:
        return
    else:
        curNode = self.head
        while(curNode):
            if curNode.data == posele:
                print("已执行")
                new_node = Node(data)
                new_node.data = data
                new_node.next = curNode.next
                curNode.next = new_node
                return
            else:
                curNode = curNode.next
```

- 删除元素

```python
#删除元素
def delete(self,posele):
      if not self.head:
          return
      else:
          preNode = None
          curNode = self.head
          count = 1
          while(curNode):
              if curNode.data == posele:
                  if count==1:
                      self.head = curNode.next
                      return
                  else:
                      preNode.next = curNode.next
                      return
              else:
                  count += 1
                  preNode = curNode
                  curNode = curNode.next
```

- 实现

```python
#结点类
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        

#单链表类
class SqList:
    #创建单链表
    def __init__(self):
        self.head = None
    #添加元素
    def add(self,data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    #插入元素
    def insert(self,posele,data):
        if not self.head:
            return
        else:
            curNode = self.head
            while(curNode):
                if curNode.data == posele:
                    print("已执行")
                    new_node = Node(data)
                    new_node.data = data
                    new_node.next = curNode.next
                    curNode.next = new_node
                    return
                else:
                    curNode = curNode.next
    #删除元素
    def delete(self,posele):
          if not self.head:
              return
          else:
              preNode = None
              curNode = self.head
              count = 1
              while(curNode):
                  if curNode.data == posele:
                      if count==1:
                          self.head = curNode.next
                          return
                      else:
                          preNode.next = curNode.next
                          return
                  else:
                      count += 1
                      preNode = curNode
                      curNode = curNode.next
    #遍历单链表
    def outline(self):
        if not self.head:
            return
        else:
            curNone = self.head
            while(curNone):
                print(curNone.data)
                curNone = curNone.next
            print()
                
                
    
if __name__ == "__main__":
    while 1:
        print("1-创建单链表 2-增加元素")
        print("3-插入元素   4-删除元素")
        command = input("请输入您的指令:")
        if command == "1":
            sqlist = SqList()
            print("单链表创建成功\n1")
        elif command == "2":
            num = eval(input("您要插入的多少元素:"))
            for i in range(num):
                data = eval(input("请输入您的数据域值:"))
                sqlist.add(data)
            sqlist.outline()
        elif command == "3":
            posele = eval(input("您要到插入哪个结点元素:"))
            data = eval(input("您要插入的数据域的值:"))
            sqlist.insert(posele,data)
            sqlist.outline()
        elif command == "4":
            posele = eval(input("您要到删除哪个结点元素:"))
            sqlist.delete(posele)
            sqlist.outline()
```

#### 3.栈

##### 3.1 顺序栈-C

![](https://gitee.com/xie-mingshan/c---data-structure/raw/master/%E5%B1%95%E7%A4%BA%E5%9B%BE/%E9%A1%BA%E5%BA%8F%E6%A0%88.png)

- 初始化

```c
//初始化栈
void initSeqS(SeqStack *sta)
{
    sta->top = -1;
    sta->length = 0;
}
```

- 入栈

```c
void push(SeqStack *sta)
{
    //获取入栈数据
    int data;
    printf("请输入入栈元素：");
    scanf("%d",&data);
    //判断栈是否已满
    if(sta->top == MAXSIZE-1)
    {
        printf("栈满,入栈失败");
        return;
    }
    //栈头指标+1
    sta->top++;
    //栈长度+1
    sta->length++;
    //栈头指标作为数组下标进行赋值
    sta->elements[sta->top] = data;
}
```

- 出栈

```c
//出栈
void pop(SeqStack *sta)
{
    //判断栈是否为空
    if(sta->top ==-1)
    {
        printf("栈空");
        return;
    }
    //栈头指标-1
    sta->top--;
    //栈长度-1
    sta->length--;
}
```

- 实现

```c
#include <stdio.h>
#define MAXSIZE 100
//栈的元素类型
typedef int Eletype;

//栈的结构体类
typedef struct SeqStack{
    int top;
    int length;
    Eletype elements[MAXSIZE];
}SeqStack;

//声明初始化栈函数
void initSeqS(SeqStack *sta);
//声明入栈函数
void push(SeqStack *sta);
//声明出栈函数
void pop(SeqStack *sta);
//声明遍历栈函数
void outline(SeqStack *sta);

int main()
{
    int command;
    SeqStack sta;
    while(1)
    {
        printf("\n\n1-初始化栈      2-元素入栈\n");
        printf("3-元素出栈      4-退出程序\n");
        printf("请输入您的操作：");
        scanf("%d",&command);
        switch(command)
        {
            //初始化栈
            case 1:
                initSeqS(&sta);
                printf("栈初始化成功");
                break;
            //入栈
            case 2:
                push(&sta);
                outline(&sta);
                break;
            //出栈
            case 3:
                pop(&sta);
                outline(&sta);
                break;
            //退出
            default:
                break;
        }
    }
    return 0;
}

//初始化栈
void initSeqS(SeqStack *sta)
{
    sta->top = -1;
    sta->length = 0;
}

//入栈
void push(SeqStack *sta)
{
    //获取入栈数据
    int data;
    printf("请输入入栈元素：");
    scanf("%d",&data);
    //判断栈是否已满
    if(sta->top == MAXSIZE-1)
    {
        printf("栈满,入栈失败");
        return;
    }
    //栈头指标+1
    sta->top++;
    //栈长度+1
    sta->length++;
    //栈头指标作为数组下标进行赋值
    sta->elements[sta->top] = data;
}

//出栈
void pop(SeqStack *sta)
{
    //判断栈是否为空
    if(sta->top ==-1)
    {
        printf("栈空");
        return;
    }
    //栈头指标-1
    sta->top--;
    //栈长度-1
    sta->length--;
}

//打印信息
void outline(SeqStack *sta)
{
    //判断栈是否为空
    if(sta->top ==-1) return;
    printf("======栈元素======\n");
    //遍历栈结点
    for(int i=sta->length-1;i>-1;i--)
    {
        printf("%d\n",sta->elements[i]);
    }
    printf("\n======栈元素======\n");

}
```

##### 3.2 顺序栈-P

- 初始化

```python
#初始化
def __init__(self,MAXSIZE = 100):
    self.top = -1
    self.elements = MAXSIZE*[0]
    self.length = 0
```

- 入栈

```python
#入栈
def push(self):
    data = input("请输入入栈元素")
    if self.top ==  len(self.elements)-1:
        return
    self.top+=1
    self.length+=1
    self.elements[self.top] = data
```

- 出栈

```python
#出栈
def pop(self):
    if self.top == -1:
        return
    self.top-=1
    self.length-=1
```

- 实现

```python
#顺序栈
class SeqStack:
    #初始化
    def __init__(self,MAXSIZE = 100):
        self.top = -1
        self.elements = MAXSIZE*[0]
        self.length = 0
    #入栈
    def push(self):
        data = input("请输入入栈元素")
        if self.top ==  len(self.elements)-1:
            return
        self.top+=1
        self.length+=1
        self.elements[self.top] = data
    #出栈
    def pop(self):
        if self.top == -1:
            return
        self.top-=1
        self.length-=1
    #遍历
    def outline(self):
        print("========栈元素========")
        for i in range(self.length-1,-1,-1):
            print(self.elements[i])
        print("=====================")
            
        
if __name__ == "__main__":
    while 1:
        print("\n1-初始化栈      2-元素入栈")
        print("3-元素出栈      4-退出程序\n")
        command = input("请输入您的操作：")
        if(command=="1"):
           sta = SeqStack()
           print("初始化成功")
        elif(command=="2"):
            sta.push()
            sta.outline()
        elif(command=="3"):
            sta.pop()
            sta.outline()
        elif(command=="4"):
            break
```

##### 3.3 链栈-C

![](https://gitee.com/xie-mingshan/c---data-structure/raw/master/%E5%B1%95%E7%A4%BA%E5%9B%BE/%E9%93%BE%E6%A0%88.png)

- 初始化

```c
void initLt(LinkStack *linkSt)
{
    //头指针为空
    linkSt->top = NULL;
    //栈长度为空
    linkSt->length = 0;
}
```

- 入栈

```c
//入栈
void pushNode(LinkStack *linkSt)
{
    //获取入栈的结点数据
    int data;
    printf("请输入元素数据：");
    scanf("%d",&data);
    //获取入栈的结点
    Node *newNode = (Node*)malloc(sizeof(Node));
    //赋值结点数据
    newNode->data = data;
    //赋值头指针给结点指针域
    newNode->next = linkSt->top;
    //头结点重新指向入栈结点
    linkSt->top = newNode;
    //栈长度+1
    linkSt->length++;
}
```

- 出栈

```c
//出栈
void popNode(LinkStack *linkSt)
{
    //判断栈是否为空,空则不出栈
    if(!(linkSt->top)) return;
    //把当前头指针赋值
    Node *curNode = linkSt->top;
    //头指针指向下一个结点
    linkSt->top = curNode->next;
    free(curNode);
}
```

- 实现

```c
#include <stdio.h>
#include <stdlib.h>

typedef int eletype;

//结点
typedef struct Node{
    eletype data;
    struct Node *next;
}Node;

//链栈
typedef struct LinkStack{
    Node *top;
    int length;
}LinkStack;


//初始化
void initLt(LinkStack *linkSt);
//入栈
void pushNode(LinkStack *linkSt);
//出栈
void popNode(LinkStack *linkSt);
//遍历
void outline(LinkStack *linkSt);

int main()
{
    int command = 0;
    LinkStack linkSt;
    while(command != 4)
    {
        printf("\n\n1-初始链栈      2-元素入栈\n");
        printf("3-元素出栈      4-退出程序\n");
        printf("请输入您的指令：");
        scanf("%d",&command);
        switch(command)
        {
            case 1:
                initLt(&linkSt);
                printf("初始化成功");
                break;
            case 2:
                pushNode(&linkSt);
                outline(&linkSt);
                break;
            case 3:
                popNode(&linkSt);
                outline(&linkSt);
                break;
            default:
                break;
        }
    }
    return 0;
}

//初始化
void initLt(LinkStack *linkSt)
{
    //头指针为空
    linkSt->top = NULL;
    //栈长度为空
    linkSt->length = 0;
}

//入栈
void pushNode(LinkStack *linkSt)
{
    //获取入栈的结点数据
    int data;
    printf("请输入元素数据：");
    scanf("%d",&data);
    //获取入栈的结点
    Node *newNode = (Node*)malloc(sizeof(Node));
    //赋值结点数据
    newNode->data = data;
    //赋值头指针给结点指针域
    newNode->next = linkSt->top;
    //头结点重新指向入栈结点
    linkSt->top = newNode;
    //栈长度+1
    linkSt->length++;
}

//出栈
void popNode(LinkStack *linkSt)
{
    //判断栈是否为空,空则不出栈
    if(!(linkSt->top)) return;
    //把当前头指针赋值
    Node *curNode = linkSt->top;
    //头指针指向下一个结点
    linkSt->top = curNode->next;
    free(curNode);
}

//遍历
void outline(LinkStack *linkSt)
{
    //判断栈是否为空,空则不遍历
    if(!(linkSt->top)) return;
    //把头指针赋值
    Node *curNode = linkSt->top;
    printf("\n=======链栈元素=======\n");
    //遍历栈里面每个结点
    while(curNode)
    {
        printf("%d\n",curNode->data);
        curNode = curNode->next;
    }
    printf("\n======================\n");
}
```



##### 3.4 链栈-P

- 初始化

```python
def __init__(self):
    #头指针
    self.top = None
    #链栈长度
    self.length = 0
```

- 入栈

```python
def push(self):
    #获取新结点
    data = input("请输入结点数据：")
    newNode = Node(data)
    newNode.next = self.top
    #头指针指向新结点
    self.top = newNode
    #链栈长度+1
    self.length += 1
```

- 出栈

```python
def pop(self):
    #判断栈是否为空
    curNode = self.top
    if not curNode:
        return
    self.top = curNode.next
    self.length -= 1
```

- 实现

```python
#结点
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
#链栈
class LinkStack:
    def __init__(self):
        #头指针
        self.top = None
        #链栈长度
        self.length = 0
    #进栈
    def push(self):
        #获取新结点
        data = input("请输入结点数据：")
        newNode = Node(data)
        newNode.next = self.top
        #头指针指向新结点
        self.top = newNode
        #链栈长度+1
        self.length += 1
    #出栈
    def pop(self):
        #判断栈是否为空
        curNode = self.top
        if not curNode:
            return
        self.top = curNode.next
        self.length -= 1
    #遍历
    def outline(self):
        #判断栈是否为空
        curNode = self.top
        if not curNode:
            return
        print("===========栈的元素===========")
        while(curNode):
            print(curNode.data)
            curNode = curNode.next
        print("=============================")
        

if __name__ == "__main__":   
    while 1:
        print("1-初始链栈   2-元素入栈")
        print("3-元素出栈   4-退出程序")
        command=  input("请输入您的指令：")
        if(command=="1"):
            lSt = LinkStack()
            print("初始化成功")
        elif(command=="2"):
            lSt.push()
            lSt.outline()
        elif(command=="3"):
            lSt.pop()
            lSt.outline()
        else:
            break
```