C++实现链表与顺序表、栈，队列

旧城等待， 2023-10-11 17:52 18阅读 0赞

*  实现头插法的单向链表

#include <stdio.h> 
    #include<malloc.h>
    
    typedef struct Node{
        
        int data;
        struct Node * next;
    }LNode,* LinkList ;
    
    void initList(LinkList &l){
        
        l = (LinkList)malloc(sizeof(LinkList));
        //手动赋值next节点，否则可能会有野指针问题
        l->next = NULL;
    }
    
    void insertHead(LinkList &l){
        
        int num;
        while (true){
        
        printf("please input a num : ");
        scanf("%d",&num);
            if (num == 0){
        
                //结束循环
                break;
            }
            
            //构建节点
            LNode * node = (LNode *)malloc(sizeof(LNode));
            node->data = num;
            //新节点的next节点指向头节点的next节点
            node->next = l->next;
            //头节点的next指向新节点
            l->next = node;
        }
    }
    
    void printList(LinkList l){
        
        while (l->next != NULL){
        
            l = l->next;
            printf("%d\n",l->data);
        }
    }
    
    
    int main(){
        
    
        //定义一个带头节点的单项链表
        LinkList l;
        //初始化头节点
        initList(l);
        //调用函数，进行头插
        insertHead(l);
        //打印节点
        printList(l);
        printList(l);
    
    }

*  实现尾插法的单向链表

#include "stdio.h"
    #include<malloc.h>
    
    
    typedef struct Node {
        
        int data;
        struct Node *next;
    } LNode, *LinkList;
    
    void initList(LinkList &l) {
        
        l = (LinkList) malloc(sizeof(LinkList));
        l->next = NULL;
    }
    
    void appendNode(LinkList &head, LinkList &tail) {
        
        int num;
        while (1) {
        
            printf("%s\n", "please input a num : ");
            scanf("%d", &num);
            if (num == 0) {
        
                break;
            }
            //创建一个新节点
            LNode *node = (LNode *) malloc(sizeof(LNode *));
            node->data = num;
            node->next = NULL;
            if (head->next == NULL || tail->next == NULL) {
        
                //第一次插入节点
                head->next = node;
                tail->next = node;
                continue;
            }
            //让尾节点的next.next等于新节点
            tail->next->next = node;
            tail = tail->next;
        }
    
    }
    
    void printNode(LinkList l) {
        
        while (l->next != NULL) {
        
            l = l->next;
            printf("%d\n", l->data);
        }
    }
    
    int main() {
        
        //定义一个单链表
        LinkList head;
        LinkList tail;
    
        //初始化单链表
        initList(head);
        initList(tail);
        //循环插入
        appendNode(head, tail);
        //打印输出
        printNode(head);
    
    }

*  实现尾插法的双向链表

#include "stdio.h"
    #include "malloc.h"
    
    
    typedef struct Node {
        
        int data;
        struct Node *next,*pre;
    } LNode, *LinkList;
    
    void initList(LinkList &l) {
        
        l = (LinkList) malloc(sizeof(LinkList));
        l->next = NULL;
        l->pre = NULL;
    }
    
    void appendNode(LinkList &head, LinkList &tail) {
        
        int num;
        while (1) {
        
            printf("%s\n", "please input a num : ");
            scanf("%d", &num);
            if (num == 0) {
        
                break;
            }
            //创建一个新节点
            LNode *node = (LNode *) malloc(sizeof(LNode *));
            node->data = num;
            node->next = NULL;
            node->pre = NULL;
            //判断是否是第一次插入
            if (head->next == NULL || tail->pre == NULL){
        
                //头结点的next指向新节点
                head->next = node;
                //新节点的pre指向头结点
                node->pre = head;
                //新节点的next指向tail
                node->next = tail;
                //tail节点的pre指向node
                tail->pre = node;
                continue;
            }
            //从二次开始插入新节点
            node->next = tail;
            tail->pre->next = node;
            node->pre = tail->pre;
            tail->pre = node;
        }
    
    }
    
    void printNode(LinkList l,LinkList tail) {
        
        while (l->next != NULL && l -> next -> next != NULL) {
        //因为双向链表的尾节点不保存数据 
            l = l->next;
            printf("%d\n", l->data);
        }
    }
    
    //删除第i个元素，那么需要找到第i - 1个元素 
    void deleteNode(LinkList &l,int index){
        
    	LinkList start = l;
    	int i = 0;
    	for(;i < index - 1;i++){
        
    		start = start -> next;
    	}
    	LNode * item = start -> next; 
    	//获取start的下下个节点
    	LNode * node = start -> next -> next;
    	//让start的next指向node
    	start -> next = node;
    	//让node的pre指向start 
    	node -> pre = start;
    	//释放item（被删除的节点）
    	free(item); 
    	
    }	
    
    int main() {
        
        //定义一个单链表
        LinkList head;
        LinkList tail;
    
        //初始化单链表
        initList(head);
        initList(tail);
        //循环插入
        appendNode(head, tail);
        
        //删除第i个元素
    	deleteNode(head,2); 
        
        //打印输出
        printNode(head,tail);
    
    }

*  c++实现静态链表

#include <stdio.h>
    #include<malloc.h>
    
    typedef struct Node {
        
        int data;
        int index;//下一个元素节点的index
    } LinkList;
    
    void initList(LinkList * l) {
         //数组类型在传入时，用指针类型作为形参接受即可，如果是想给数组重新赋值，则用引用类型（这点和Java中有严重区别） 
        for (int i = 0; i < 10; ++i) {
        
            LinkList item;
            item.data = 0;
            item.index = -1;
            l[i] = item;
        }
    }
    
    bool isEmpty(LinkList * l){
        
        return l[0].index == -1;
    }
    
    void insertHead(LinkList &l) {
        
    
    }
    
    void printList(LinkList * l) {
        
        int index = l[0].index;
        if (index == -1){
        
            return;
        }
        LinkList start = l[0];
        while ( start.index != -1 ){
        
        	  start = l[start.index];
            //输出data值
            printf(" %d \n", start.data );
        }
    
    }
    
    
    int main() {
        
    
        //定义一个静态链表
        LinkList l[10];
        
        initList(l);
    
        //定义几个节点
        LinkList item1 = {
        10,5};
        LinkList item2 = {
        15,2};
        LinkList item3 = {
        20,-1};
    
        l[0].index = 3;
        l[3] = item1;
        l[5] = item2;
        l[2] = item3;
    
        printList(l);
        
        return -1;
    
    }

##### 链表与顺序表的比较 #####

顺序表是使用顺序存储方式实现的线性表，逻辑结构上是连续的，而物理结构上也是连续的，而链表在逻辑结构上是连续的，但是在物理结构上是离散的，链表的存储密度更低，因为链表的节点除了要存储数据节点以外还要存储一个指针节点指向下一个节点的地址。顺序表的查找时间复杂度为o(1),找到了头节点的地址，可直接根据数据类型计算出第i处节点的地址直接查找到，而链表的查找时间复杂度为o(n)，因为链表只能从头节点开始一个一个的进行遍历，顺序表的增加和删除的时间复杂度为o(n)，这个n主要是集中在移动节点上，因为要新增节点，首先要把该节点往后的节点依次后移。而链表的删除和增加的时间复杂度为o(n)，虽然链表的也是o(n)，但是链表的n主要是花费在指针移动上，指针移动的速度可远远比顺序表移动元素的速度快多了。所以链表得插入和删除时间复杂度为o(n)也更快与顺序表。

#### 栈 ####

*  顺序栈实现

#include "stdio.h"
    
    
    //定义一个结构体，使用顺序存储的方式实现栈（顺序栈）
     struct Stack{
        
            int position;//栈顶指针
            int data[10]; //元素
    };
    
    void initStack(Stack &s) {
        
        s.position = -1;
    }
    
    void addDataToStack(Stack &s) {
        
        int num;
        while (1) {
        
        	printf("%s","please input a num :");
            scanf("%d", &num);
            if (num == 0) {
        
                break;
            }
            //往栈顶入元素
            if (s.position == 9) {
        
                printf("%s\n", "the stack has fulled 10 elements , insert data error !");
                break;
            }
            //指针移动，压入元素
            s.data[++s.position] = num;
            printf(" current position = %d \n ",s.position);
        }
    }
    
    void printStack(Stack stack) {
        
        if (stack.position == -1) {
        
            printf("%s\n", "there is no element to print !");
            return;
        }
        while (stack.position != -1) {
        
            int element = stack.data[stack.position--];
            printf("%d\n", element);
        }
    
    }
    
    int main() {
        
    
        //定义一个栈
        Stack s;
        //初始化一个栈
        initStack(s);
        //添加元素
        addDataToStack(s);
        printStack(s);
        
    }

*  链式存储方式实现栈 **(头结点初始化时一定也要用malloc函数分配，头结点初始化时一定也要用malloc函数分配，头结点初始化时一定也要用malloc函数分配，头结点初始化时一定也要用malloc函数分配，头结点初始化时一定也要用malloc函数分配)**

#include "stdio.h"
    #include "malloc.h" 
    
    //定义一个结构体，使用顺序存储的方式实现栈（顺序栈）
    typedef struct Node{
        
        int data;
        struct Node * next;
    }* Stack;
    
    void appendNode(Stack &stack){
        
    	  stack= (Stack)malloc(sizeof(Stack));//头结点也一定要初始化 
    	 stack->next = NULL;
        int num;
        while (true){
        
        	printf("%s","please input a num ： ");
            scanf("%d",&num);
            if(num == 0){
        
                break;
            }
            //malloc申请一片新空间
            Stack node = (Stack)malloc(sizeof(Stack));
            node->data = num;
            //新节点的next指向头结点的next
            node->next = stack->next;
            //头结点的next指向新节点
            stack->next = node;
        }
    }
    
    void printNode(Stack stack){
        
        while (stack->next != NULL){
        
            stack = stack->next;
            printf("%d\n",stack->data);
        }
    }
    
    int main() {
        
    
        //定义一个链式栈
        Stack stack;
        //初始化一个链式栈
        
      //  initStack(stack);
        //添加元素
        appendNode(stack);
        //打印元素
        printNode(stack);
        
    }

### 队列 ###

*  顺序存储方式实现队列

#include "stdio.h"
    
    #define MAXSIZE 5
    typedef struct Queue {
        
        int head;//队列头指针,指向队列最先存入的元素
        int tail;//队列尾指针，指向待存入元素的下标
        int data[MAXSIZE];//队列容量
    } Queue;
    
    
    //初始化，头指针和尾指针都是0
    void initQueue(Queue &q) {
        
        q.head = 0;
        q.tail = 0;
    }
    
    //判断一个队列是否为一个空队列
    bool isEmpty(Queue q) {
        
        return q.tail == q.head;
    }
    
    //判断一个循环队列是否已满，如果要实现循环队列，则需要牺牲一个存储单元，例如最大10个，现在只能存9个，才能实现循环队列
    bool isFullQueue(Queue queue) {
        
        return (queue.tail + 1) % MAXSIZE == queue.head;
    }
    
    //入队
    bool enQueue(Queue &q, int data) {
        
        if (isFullQueue(q)) {
        //队列已经满了
            printf(" %s \n", "queue is full");
            return false;
        }
        //插入新元素，在tail处插入，让tail++
        q.data[q.tail] = data;
        //此时让tail等于 （ tail + 1 ） % MAXSIZE，maxsize是10，tail如果现在指向9，那么下标9添加上元素以后tail+1 % 10 = 0，那么此时tail又回到了下标0处的位置，这样就实现了循环队列
        q.tail = (q.tail + 1) % MAXSIZE;
        return true;
    }
    
    //出队操作
    bool deQueue(Queue &q,int &element){
        
        if(isEmpty(q)){
        
            printf(" %s \n", "queue is empty" );
            return false;
        }
        //将删除的元素返回
        element = q.data[q.head];
        //让head = (head + 1) % MAXSIZE 整个存取都是一个转圈循环的过程，因为队列不能随机插入，只能从队尾删除 对头插入，所以很好想
        q.head = (q.head + 1) % MAXSIZE;
    }
    
    //获取队列的第一个元素
    bool getTopData(Queue queue,int data){
        
        //返回队列的第一个元素
        if(isEmpty(queue)){
        
            printf(" %s \n", "queue is empty" );
            return false;
        }
        data = queue.data[queue.head];
    }
    
    void operationQueue(Queue &q){
        
        char num;
        while(true){
        
            printf("%s","please choose operation : a : enter , b : pop , c : getTop "); 
            scanf("%c",&num);
            if(num == 'a'){
        
                int data;
                printf("%s","please input a num : ");
                scanf("%d",&data);
                enQueue(q,data);
            }else if (num == 'b'){
        
                int data;
                deQueue(q,data);
                printf("%s%d\n","pop element : ",data);
            }else {
        
                int data;
                getTopData(q,data);
                printf("%s%d\n","top element : ",data);
            }
        }
    }
    
    int main() {
        
    
        //声明一个队列
        Queue queue;
        //初始化一个队列
        initQueue(queue);
        //队列操作
        //operationQueue(queue);
        enQueue(queue,10);
        enQueue(queue,20);
        enQueue(queue,30);
         enQueue(queue,30);
          enQueue(queue,30);
           enQueue(queue,30);
            enQueue(queue,30);
        
        int data;
        deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
        
    
        return 0;
    }

循环队列判断队列中的元素个数： (tail + MAXSIZE - head) % MAXSIZE,所以说这个公式也是最大只能到9.

**如何在不牺牲一个存储元素的情况下实现循环队列**  
此时需要添加一个辅助变量size，当两个指针相同，且size等于maxsize时，才算满，实现代码如下，此时注意在入队列或出队列时，size的值要±

#include "stdio.h"
    
    #define MAXSIZE 5
    typedef struct Queue {
        
        int head;//队列头指针,指向队列最先存入的元素
        int tail;//队列尾指针，指向待存入元素的下标
        int data[MAXSIZE];//队列容量
        int size;
    } Queue;
    
    
    //初始化，头指针和尾指针都是0
    void initQueue(Queue &q) {
        
        q.head = 0;
        q.tail = 0;
        q.size = 0;
    }
    
    //判断一个队列是否为一个空队列
    bool isEmpty(Queue q) {
        
        return ( q.tail == q.head ) && q.size == 0 ;
    }
    
    //判断一个循环队列是否已满，如果要实现循环队列，则需要牺牲一个存储单元，例如最大10个，现在只能存9个，才能实现循环队列
    bool isFullQueue(Queue q) {
        
        //return ( (queue.tail + 1) % MAXSIZE == queue.head ) && queue.size == MAXSIZE ;
        return ( q.tail == q.head ) && q.size == MAXSIZE ;
    }
    
    //入队
    bool enQueue(Queue &q, int data) {
        
        if (isFullQueue(q)) {
        //队列已经满了
            printf(" %s \n", "queue is full");
            return false;
        }
        //插入新元素，在tail处插入，让tail++
        q.data[q.tail] = data;
        //此时让tail等于 （ tail + 1 ） % MAXSIZE，maxsize是10，tail如果现在指向9，那么下标9添加上元素以后tail+1 % 10 = 0，那么此时tail又回到了下标0处的位置，这样就实现了循环队列
        q.tail = (q.tail + 1) % MAXSIZE;
        q.size++;
        return true;
    }
    
    //出队操作
    bool deQueue(Queue &q,int &element){
        
        if(isEmpty(q)){
        
            printf(" %s \n", "queue is empty" );
            return false;
        }
        //将删除的元素返回
        element = q.data[q.head];
        //让head = (head + 1) % MAXSIZE 整个存取都是一个转圈循环的过程，因为队列不能随机插入，只能从队尾删除 对头插入，所以很好想
        q.head = (q.head + 1) % MAXSIZE;
        q.size--;
    }
    
    //获取队列的第一个元素
    bool getTopData(Queue queue,int data){
        
        //返回队列的第一个元素
        if(isEmpty(queue)){
        
            printf(" %s \n", "queue is empty" );
            return false;
        }
        data = queue.data[queue.head];
    }
    
    void operationQueue(Queue &q){
        
        char num;
        while(true){
        
            printf("%s","please choose operation : a : enter , b : pop , c : getTop "); 
            scanf("%c",&num);
            if(num == 'a'){
        
                int data;
                printf("%s","please input a num : ");
                scanf("%d",&data);
                enQueue(q,data);
            }else if (num == 'b'){
        
                int data;
                deQueue(q,data);
                printf("%s%d\n","pop element : ",data);
            }else {
        
                int data;
                getTopData(q,data);
                printf("%s%d\n","top element : ",data);
            }
        }
    }
    
    int main() {
        
    
        //声明一个队列
        Queue queue;
        //初始化一个队列
        initQueue(queue);
        //队列操作
        //operationQueue(queue);
        enQueue(queue,10);
        enQueue(queue,20);
        enQueue(queue,30);
         enQueue(queue,40);
          enQueue(queue,50);
           enQueue(queue,60);
            enQueue(queue,70);
        
        int data;
        deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
         deQueue(queue,data);
        printf("%d\n",data);
    
        return 0;
    }

*  链式方式实现队列（单链表尾插法）

#include "stdio.h"
    #include "malloc.h"
    
    
    //使用非线性存储的方式实现duilie
    typedef struct Node{
        
        int data;
        struct Node * next;
    }QNode,*Queue;
    
    //初始化队列，注意指针类型，头结点的初始化也需要分配空间
    void initQueue(Queue &q){
        
        q = (Queue)malloc(sizeof(Queue));
        q->next = NULL;
    }
    
    void appendElement(Queue &q){
        
        Queue tail = q;//定义一个尾节点
        int num;
        while (1){
        
            scanf("%d",&num);
            if (num == 0){
        
                break;
            }
            QNode * node = (QNode *)malloc(sizeof(QNode *));
            node -> next = NULL;
            node -> data = num;
            //判断是否是第一次添加
            if(q->next == NULL){
        
                q->next = node;
                tail->next = node;
                continue;
            }
           // printf("%s\n","111");
            //如果不是第一次添加
            tail->next->next = node;
            tail = tail->next ;//调整尾节点的位置
        }
    }
    
    void printQueue(Queue q){
        
        while (q->next != NULL){
        
            q = q->next;
            printf("%d",q->data);
        }
    }
    
    int main(){
        
       
        //定义一个链式队列
        Queue queue;
        //初始化一个链式队列
        initQueue(queue);
        //添加元素
        appendElement(queue);
        //打印输出
        printQueue(queue);
        return 0;
    }

*  链式队列的添加和删除，删除时，注意移动头指针

#include "stdio.h"
    #include "malloc.h"
    
    //队列节点
    typedef struct QNode{
        
        int data;
        struct QNode * next;
    } * Queue;
    
    //队列
    typedef struct LinkQueue{
        
        Queue head; //头节点
        Queue tail; //尾节点
    };
    
    void initLinkQueue(LinkQueue &linkQueue){
        
        linkQueue.head = linkQueue.tail = (Queue)malloc(sizeof(Queue));//创建头节点和尾节点
        linkQueue.tail->next = NULL;
    }
    
    void appendNode(LinkQueue &linkQueue){
        
        int num;
        while (true){
        
            printf("%s","please input a num : ");
            scanf("%d",&num);
            if(num == 0){
        
                break;
            }
            //创建新节点
            QNode * node = (QNode *)malloc(sizeof(QNode *));
            node->data = num;
            node -> next = NULL;
            //由于头节点和尾节点都指向了一个节点，此处只修改尾节点的next，也影响头节点指向的那个next
            linkQueue.tail->next = node;
            linkQueue.tail = node;//修改表尾指针
        }
    }
    
    void deleteNode(LinkQueue &linkQueue){
        
        QNode * tail = linkQueue.tail;
        QNode * head = linkQueue.head;
        while (true){
        
        	printf("%s\n","hhhh");
            if(tail == head){
        
                printf(" %s \n", "queue is empty !" );
                break;
            }
            QNode * deleteNode = head->next;//删除头节点指向的元素
            printf("%d\n",deleteNode->data);
    		head->next = head->next->next;
            //判断删除的这个节点是否等于尾节点
    		if(deleteNode == tail){
        
    			linkQueue.tail = linkQueue.head;
    		} 
            free(deleteNode);
        }
    
    }
    
    int main(){
        
        //定义一个带头节点和尾节点的队列
        LinkQueue linkQueue;
        //初始化头节点和尾节点
        initLinkQueue(linkQueue);
        //添加节点
        appendNode(linkQueue);
        //删除节点
        deleteNode(linkQueue);
    
        return 0;
    }

c++ 实现逆波兰表达式求值

#include "stdio.h"
    #include "malloc.h"
    #include <stdlib.h>
    
    #define MAXSIZE 20
    //顺序栈
    typedef struct Node {
        
        int length;
        char str[MAXSIZE];
    } Stack;
    
    //初始化一个顺序栈
    void initStack(Stack &stack) {
        
        stack.length = 0;
        for (int i = 0; i < MAXSIZE; i++) {
        
            stack.str[i] = '\0';
    //        for (int j = 0; j < MAXSIZE; ++j) {
        
    //            stack.str[i][j] = '\0';
    //        }
        }
    }
    
    //压栈
    void push(Stack &stack, char character) {
        
    	printf("入栈元素 %c \n",character);
        stack.str[stack.length++] = character;
    }
    
    //弹栈
    void pop(Stack &stack, char &character) {
        
        if (stack.length <= 0) {
        
            return;
        }
        character = stack.str[--stack.length];
    }
    
    
    int main() {
        
    
        //定义栈
        Stack stack;
        initStack(stack);
        //逆波兰表达式
        char str[] = "84/23*+1-";
        //char str[][] = {
        {"8"}, {"4"}, {"/"}, {"2"}, {"3"}, {"*"}, {"+"}, {"1"}, {"-"}};
        //遍历每一个一维数组
        int size = sizeof(str) / sizeof(str[0]);
        for (int i = 0; str[i] != '\0'; ++i) {
        
            char item = str[i];
            if (item == '+' || item == '-' || item == '*' || item == '/') {
        
                //弹栈，弹出2个元素，这里注意要有严格的顺序要求,否则在做除法的时候会有异常 
                char firstChar;
                pop(stack, firstChar);
                int firstElem = firstChar - '0';//char型字符转int
                char secondChar;
                pop(stack, secondChar);
                int secondElem = secondChar - '0';
    			//printf("弹出的第一个元素 %d ， 弹出的第二个元素 %d",firstElem,secondElem);
                //判断操作符
                int result = 0;
                switch (item) {
        
    				case '+': {
        
    					result = secondElem + firstElem ;
                    }
                        break;
                    case '-': {
        
                    		result = secondElem - firstElem;
                    }
                        break;
                    case '*': {
        
                    		result = secondElem * firstElem ;
                    }
                        break;
                    case '/': {
        
                    		result = secondElem /  firstElem;
                    }
                        break;
    
    
                }
    			//将结果压栈
    			char res = result + '0'; //int转char 
    			//printf("当前求和结果 %c \n",res);
    			push(stack,res); 
    
            } else {
        
                //压栈
                push(stack, item);
            }
    
        }
    
    	char data ;
    	pop(stack,data);
    	printf("结果是 ：%c ",data);
    
        return 0;
    }

*  注意问题

--------------------

1.判断字符串结束时用 str[i] != '/0'
    2.char型数字转int，int型数组转char
    3.注意弹栈时元素的顺序（在做除法时，一定是后弹栈的 / 先弹栈的）

--------------------