c/c++单链表的创建及操作_c++链表的创建与操作

大一下期第二次数据结构单链表实验代码
case 2及case 5处仍存在问题待解决

/*1、创建一个带头结点的单链表（头指针为head），且遍历此链表（输出链表中各结点的值）；
      2、查找单链表中的第i个结点，并输出结点元素的值；
      3、在单链表中的第i个结点前插入一个结点值为e的正整数(从外部输入);
      4、删除单链表中的第j个结点；
      *5、将单链表中的各结点就地逆序（不允许另建一个链表）；
*/
#define OK 1
#define ERROR -1
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;
typedef struct LNode   //单链表存储结构
{
    int data;     //结点数据域
    struct LNode *next;//结点的指针域
}LNode,*LinkList;
LNode head;
int ListInit(LinkList &head)//构造一个空的单链表L
{
    head=new LNode;//生成新结点作为头结点，头指针head指向头结点
    head->next=NULL;//头结点指针域置空
    return OK;
}
int ListCreat_R(LinkList &head,int n)//后插法创建单链表
{
    LinkList r,p;
    r=head;
    cout<<"请输入链表的元素："<<endl;
    for(int i=0;i<n;i++)
    {
        p=new LNode;//生成新结点
        cin>>p->data;//输入元素赋值给新结点*p的数据域
        p->next=NULL;
        r->next=p;//将新结点插入尾结点*r
        r=p;//r指向新的尾结点*p
    }
    return OK;
}
int ListTraverse(LinkList &head)//遍历链表
{
    LinkList p=head->next;//初始化，p指向首元结点
    int i=0;//计数器赋值为0
    while(p)
    {
        cout<<p->data<<" ";
        p=p->next;
        i++;
    }
    if(i==0)
    {
        cout<<"链表为空！"<<endl;
        return ERROR;
    }
    return OK;
}
int GetElem(LinkList &head,int i,int &e)//按位置查找链表元素的值
{
    LinkList p=head->next;//初始化，p指向首元结点
    int j=1;//计数器j赋初值为1
    while(p&&j<1)//顺链域向后扫描直到p为空或p指向第i个元素
    {
        p=p->next;//p指向下一个结点
        ++j;//计数器加一
    }
    if(!p||j>i)//i值不合法
        return ERROR;
    e=p->data;//取第i个结点的数据域
    return OK;
}
int ListInsert(LinkList &head,int i,int e)//在链表第i个位置插入值为e的新结点
{
    LinkList p=head,s;
    int j=0;
    while(p&&(j<i-1))//查找第i-1个结点，令p指向该结点
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i-1)//i值不合法返回ERROR
        return ERROR;
    s=new LNode;//生成新结点*s
    s->data=e;//*s的数据域为e
    s->next=p->next;//*s指针域指向结点a
    p->next=s;//*p指针域指向*s
    return OK;
}
int ListDelete(LinkList &head,int i)//在链表中删除第i个元素
{
    LinkList p=head,q;
    int j=0;
    while((p->next)&&(j<i-1))//查找第i-1个结点，并令p指向该结点
    {
        p=p->next;
        ++j;
    }
    if(!(p->next)||(j>i-1))//i值不合法
        return ERROR;
    q=p->next;//临时保存被删结点的地址以备释放
    p->next=q->next;//改变删除结点前驱结点的指针域
    free(q);//释放删除结点的空间
    return OK;
}
int ListReverse(LinkList &head)//将链表原地逆序
{
    if(head==NULL||head->next==NULL)
        return ERROR;
    else
    {
        LinkList p=head->next,q;
        head->next=NULL;
        while(p)
        {
            q=p->next;
            p->next=head;
            head=p;
            p=q;
        }
    }
    return OK;
}
int main()
{
    int c,i,e,n;
    LinkList L;
    ListInit(L);
    cout<<"请输入链表元素的个数："<<endl;
    cin>>n;
    ListCreat_R(L,n);
    cout<<"创建链表成功！"<<endl;
    cout<<"1.遍历单链表"<<endl;
    cout<<"2.按位置查找链表中的一个元素"<<endl;
    cout<<"3.在链表中插入一个元素"<<endl;
    cout<<"4.在链表中删除一个元素"<<endl;
    cout<<"5.就地逆序链表"<<endl;
    cout<<"请选择要完成的操作并输入对应序号："<<endl;
    cin>>c;
    switch(c)
    {
        case 1:
            ListTraverse(L);
            break;
        case 2:
            cout<<"请输入要查找的元素位置："<<endl;
            cin>>i;
            GetElem(L,i,e);
            cout<<e<<endl;
            break;
        case 3:
            cout<<"请输入要插入数值的位置："<<endl;
            cin>>i;
            cout<<"请输入要插入的数值："<<endl;
            cin>>e;
            ListInsert(L,i,e);
            cout<<"新链表为："<<endl;
            ListTraverse(L);
            break;
        case 4:
            cout<<"请输入要删除元素的位置："<<endl;
            cin>>i;
            ListDelete(L,i);
            cout<<"新链表为："<<endl;
            ListTraverse(L);
            break;
        case 5:
            ListReverse(L);
            cout<<"新链表为："<<endl;
            ListTraverse(L);
            break;
        default: break;
    }
    return 0;
}
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172