线性表之单链表

复制代码#include "stdafx.h" #include<iostream> using namespace std; #include<malloc.h> #define OK 1 //正确 #define ERROR 0 //失败 typedef int ElementType; typedef struct LNode{ //定义结构体 ElementType data; LNode *next; }LNode,*LinkList; //初始化单链表 void init(LinkList &L,int n) { if(n<0) return ; L = (LinkList) malloc(sizeof(LNode)); L->next=NULL;//创建头指针 int data; LinkList node; for(int i=0;i<n;i++) { cin>>data; node = (LinkList) malloc(sizeof(LNode));//创建LNode的节点 node->data=data; node->next=L->next; L->next=node; } } //获取单链表第i个位置的元素e int getElement(LinkList &L,int i,ElementType &e) { LNode *p; int j=1; p=L->next; while(p && j<i) { p=p->next; ++j; } if(!p || j>i) { cout<<"没有找到位置序号"+i; return ERROR; } e=p->data; cout<<"单链表第"<<i<<"个位置的元素是："<<e; return OK; } //删除单链表的第i个位置的元素 void insert(LinkList &L,int i,ElementType &e) { LNode *p; int j=1; LinkList node; p=L; while(p && j<i) //寻找第i-1个节点 { p=p->next; ++j; } if(!p || j>i) { cout<<"插入的位置已经超出边界"<<endl; return; } node = (LinkList) malloc(sizeof(LNode));//创建LNode的节点 node->data=e; node->next = p->next; p->next = node; } //向单链表的第i个位置插入元素e void delLink(LinkList &L,int i,ElementType &e) { LNode *p,*q; int j=1; LinkList node; p=L; while(p->next && j<i) //寻找第i节点,也可以寻找第i-1个节点 { p=p->next; ++j; } if(!(p->next)|| j>i) { cout<<"删除的位置不对"<<endl; return; } q=p->next; p->next=q->next; e=q->data; free(q); } //打印单链表的数据 void print(LinkList &L) { LNode *p; p=L->next; while(p) { cout<<p->data<<" "; p=p->next; } } int main(int argc,char* argv[]){ LinkList L; ElementType e; int n; cout<<"请输入需要创建的链表长度: "<<endl; cin>>n; cout<<"请输入"<<n<<"个数据: "; init(L,n); cout<<"创建的链表为: "; print(L); cout<<endl; cout<<"请输入需要获取链表那个位置的元素: "; cin>>n; getElement(L,n,e); cout<<"请输入要插入元素的位置和数据: "; cin>>n; cin>>e; cout<<"插入后的单链表为："<<endl; insert(L,n,e); print(L); cout<<"请输入要删除元素的位置: "; cin>>n; delLink(L,n,e); cout<<"删除后的单链表为："<<endl; print(L); print(L); cin>>n; return OK; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include  "stdafx.h"
#include<iostream>
using namespace std;
#include<malloc.h>
#define OK               1        //正确
#define ERROR            0        //失败
typedef int ElementType;

typedef  struct LNode{                //定义结构体    
    ElementType data;
    LNode *next;
}LNode,*LinkList;

//初始化单链表
void init(LinkList &L,int n)
{
    if(n<0) return ;
    L = (LinkList) malloc(sizeof(LNode));
    L->next=NULL;//创建头指针
    int data;
    LinkList node;
    for(int i=0;i<n;i++)
    {
        cin>>data;
        node = (LinkList) malloc(sizeof(LNode));//创建LNode的节点
        node->data=data;
        node->next=L->next;
        L->next=node;
    }
}
//获取单链表第i个位置的元素e
int getElement(LinkList &L,int i,ElementType &e)
{
    LNode *p;
    int j=1;
    p=L->next;
    while(p && j<i)
    {
        p=p->next;
        ++j;
    }
    if(!p || j>i)
    {
        cout<<"没有找到位置序号"+i;
        return ERROR;
    }
    e=p->data;
    cout<<"单链表第"<<i<<"个位置的元素是："<<e;
    return OK;
}
//删除单链表的第i个位置的元素
void insert(LinkList &L,int i,ElementType &e)
{
    LNode *p;
    int j=1;
    LinkList node;
    p=L;
    while(p && j<i)    //寻找第i-1个节点
    {
        p=p->next;
        ++j;
    }
    if(!p || j>i)
    {
        cout<<"插入的位置已经超出边界"<<endl;
        return;
    }
    node = (LinkList) malloc(sizeof(LNode));//创建LNode的节点
    node->data=e;
    node->next = p->next;
    p->next = node;
}
//向单链表的第i个位置插入元素e
void delLink(LinkList &L,int i,ElementType &e)
{
    LNode *p,*q;
    int j=1;
    LinkList node;
    p=L;
    while(p->next && j<i)    //寻找第i节点,也可以寻找第i-1个节点
    {
        p=p->next;
        ++j;
    }
    if(!(p->next)|| j>i)
    {
        cout<<"删除的位置不对"<<endl;
        return;
    }
    q=p->next;
    p->next=q->next;
    e=q->data;
    free(q);
}
//打印单链表的数据
void print(LinkList &L)
{
    LNode *p;
    p=L->next;
    while(p)
    {
        cout<<p->data<<"    ";
        p=p->next;
    }
}
int main(int argc,char* argv[]){
    LinkList L;
    ElementType e;
    int n;
    cout<<"请输入需要创建的链表长度: "<<endl;
    cin>>n;
    cout<<"请输入"<<n<<"个数据: ";
    init(L,n);
    cout<<"创建的链表为: ";
    print(L);
    cout<<endl;

    cout<<"请输入需要获取链表那个位置的元素: ";
    cin>>n;
    getElement(L,n,e);

    cout<<"请输入要插入元素的位置和数据: ";
    cin>>n;
    cin>>e;
    cout<<"插入后的单链表为："<<endl;
    insert(L,n,e);
    print(L);
    
    cout<<"请输入要删除元素的位置: ";
    cin>>n;
    delLink(L,n,e);
    cout<<"删除后的单链表为："<<endl;
    print(L);
    
    print(L);
    cin>>n;
    return OK;
}