首页 学习&技术

下学期就要开始学面向对象的程序设计了，也就是相当于上上学期的程序设计的 c++ 版本，所以还是要认真的对待一下这个，毕竟还是要自己好好的提升一下自己的程序能力啊。不能再继续摆了。。。开整

这个题目给我看了半天才看懂，好家伙，我本来以为说的是要让我实现里面要求的功能，结果看完之后发现实际上要求的是得把他题目附加的两个条件满足了，也就是说虽然题目中没有明确写出他的那些操作指令的具体实现过程，但是我们默认是已经实现了的，同时我们需要在附加条件中实现所需要的另外两个要求 (单项链表、堆栈、队列三选二)，然后最重要的是要体现代码重用的思想，也就是我们需要尽量使用之前所写出来的那些指令，通过改造来实现后两种的基础指令合集。

1
2
3
4
5
6
7
8
9
10
1）	至少实现堆栈、队列、单向链表中的两个类型（包括数据结构类型名、基本操作集合）；
2）	实现语言不限； 
对于要实现的每个类型，你也可以使用 C 的 struct 定义其结构，全局函数定义其操作；
3）	要体现“模块”划分、模块与源程序文件的对应关系；
 应在提交的解答中进行说明，不要让老师猜测！！！
4）	要体现“代码重用”的思想（即使用/调用 已有的数据结构、函数等）。
重用的一种表现之举例：
就像你调用C语言例程库中的 fopen、fclose、fprintf等函数那样，你实际在重用这些函数，来实现你所需要的功能。
5）	应给出必要的说明（注释），便于老师理解批阅。

就是上面的这段话。。。。

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
#include<iostream>
using namespace std;
struct  Dlist {        // 双向链表结点的数据结构
	struct Dlist * prev; // 当前结点的前驱结点
	struct Dlist * next; // 当前结点的后继结点
	int   appValue;  // 这是应用数据，假设仅接受非负整数
};

//链表操作1：newDlist
//  生成一个双向链表的第一个结点，其中存储了整数 n。
//  返回指向该结点的指针。该指针将用作后续各函数的参数。
struct Dlist * newDlist(int n);

/* 下面函数的参数中， ptrList 为指向链表表头结点的指针 */
//链表操作2：addFirst
//  将整数 n 插入到双向链表的最前面，即为链表添加新的头结点，其中存储n。
//  返回指向新的头结点的指针。
struct Dlist * addFirst(struct Dlist * ptrList, int n);

//链表操作3：append
//  将整数 n 追加到链表末尾，即增加新的尾结点，其中存储 n 。
//  返回指向新的尾结点指针。
struct Dlist * append(struct Dlist * ptrList,  int n);

//链表操作4：removeHead
//  删除链表头结点，返回指向新的头结点指针。
//  若删除前 or 删除后链表为空，则返回 NULL。
struct Dlist * removeHead(struct Dlist * ptrList);

//链表操作5：removeTail
//  删除链表尾结点，返回指向新的尾结点的指针。
//  若删除前 or 删除后链表为空，则返回 NULL。
struct Dlist * removeTail(struct Dlist * ptrList);

//链表操作6：sizeOfDlist
//  返回链表中包含的结点个数，若链表为空（ptrList==NULL）则返回0
int  sizeOfDlist(struct Dlist * ptrList);

//链表操作7：destroyDlist
//  销毁链表整体并释放其占用的内存空间，若链表为空则什么也不做
void  destroyDlist(struct Dlist * ptrList);

这是给出的代码片段，现在就开始实现吧。。

首先开始实现最简单的单项链表：

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
typedef struct linklist
{//单项列表的数据结构
    int data;//用来储存数据
    struct linklist *next;//指向下一节点的指针
};
//链表操作1：new
//  生成一个双向链表的第一个结点，其中存储了整数 n。
//  返回指向该结点的指针。该指针将用作后续各函数的参数。
struct  linklist *newlist(int n)
{
    linklist *head = NULL;
    head = (linklist *)malloc(sizeof(linklist));
    head->data = n;
    head->next = NULL;
    return head;
}
/* 下面函数的参数中， hdlist 为指向链表表头结点的指针 */
//链表操作2：addhead
//  将整数 n 插入到单向链表的最前面，即为链表添加新的头结点，其中存储n。
//  返回指向新的头结点的指针。
struct linklist *addhead(struct linklist *hdlist, int n)
{
    linklist *p = NULL;//创建新节点
    p = (linklist *)malloc(sizeof(linklist));
    p->next = hdlist;//让新创建的节点插入到表头上
    p->data = n;//赋值
    return hdlist;
}
//链表操作3：addend
//  将整数 n 追加到链表末尾，即增加新的尾结点，其中存储 n 。
//  返回指向新的尾结点指针。
struct linklist *addend(struct linklist *last, int n)//last为指向尾节点的指针
{
    linklist *p = NULL;
    p = (linklist *)malloc(sizeof(linklist));
    last->next = p;
    p->data = n;
    last = last->next;
    return last;
};
//链表操作4：removeHead
//  删除链表头结点，返回指向新的头结点指针。
//  若删除前 or 删除后链表为空，则返回 NULL。
struct linklist *rmhead(struct linklist *hdlist)
{
    if(hdlist->next==NULL&&hdlist==NULL){
        return NULL;
    }//检查前后链表是否为空
    linklist *p = NULL;
    p = (linklist *)malloc(sizeof(linklist));
    p= hdlist->next;
    free(hdlist);
    return p;
}
//链表操作5：removeTail
//  删除链表尾结点，返回指向新的尾结点的指针。
//  若删除前 or 删除后链表为空，则返回 NULL。
struct linklist *rmend(struct linklist *hdlist)
{
    linklist *p = NULL;
    p = (linklist *)malloc(sizeof(linklist));
    linklist *q = NULL;
    q = (linklist *)malloc(sizeof(linklist));
    p = hdlist;
    if(p->next!=NULL){
        p = p->next;
    }//找到尾节点p
    if(q->next!=p){
        q = q->next;
    }//找到尾节点的前一个节点
    if (q== NULL&&p== NULL)
    {
        return NULL;
    }//检查前后链表是否为空
    q->next = NULL;
    free(p);//释放空间
    return q;//返回指向尾节点的指针
}
//链表操作6：sizeOfDlist
//  返回链表中包含的结点个数，若链表为空（ptrList==NULL）则返回0
int sumlist(struct linklist *hdlist)
{
    int sum=1;//定义整数类型用来统计节点个数
    linklist *p = NULL;
    p = (linklist *)malloc(sizeof(linklist));
    p = hdlist;//不改变头节点指针的情况下来进行遍历
    if(p->next!=NULL){
        sum += 1;
        p = p->next;
    }
    return sum;
}
//链表操作7：destroyDlist
//  销毁链表整体并释放其占用的内存空间，若链表为空则什么也不做
int dylist(struct linklist *hdlist)
{
    if(hdlist==NULL){
        return 0;
    }//判断条件
    linklist *p = NULL;
    p = (linklist *)malloc(sizeof(linklist));
    p = hdlist->next;
    free(hdlist);
    dylist(p);//递归直至链表删除完成
}

感觉这个就是基本上把功能什么的东西全都自己实现了一遍嘛。。。。虽然说好多东西自己写的时候还是忘掉了，然后就边写边查，姑且算是把东西都写出来了。话说也不是很难嘛

然后就就是开始写堆栈了，按道理来说，我连单项链表都写出来了，这个应该是更简单啊，结果写了半天还有点小问题一直在报错。。。怪，最后到截止日期都没改好。。不管了，姑且就这样子交上去吧。。。下面是代码

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
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
typedef struct SqStack{
    int data[MAXSIZE];
    int top;    //用于栈顶指针
};

struct SqStack *zhaninit(SqStack *S){
    S->top = -1;    //初始化栈顶指针
}

bool StackEmpty(SqStack S){
    if(S.top == -1){    
        return true;    //栈空
    }else{  
        return false;   //不空
    }
}
/*插入元素e为新的栈顶元素*/
struct Push(SqStack *S, ElemType e){
    //满栈
    if(S->top == MAXSIZE-1){
        return ERROR;
    }
    S->top++;   //栈顶指针增加一
    S->data[S->top] = e;    //将新插入元素赋值给栈顶空间
    return OK;
}
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqStack *S, ElemType *e){
    if(S->top == -1){
        return ERROR;
    }
    *e = S->data[S->top];   //将要删除的栈顶元素赋值给e
    S->top--;   //栈顶指针减一
    return OK;
}
/*读栈顶元素*/
Status GetTop(SqStack S, ElemType *e){
    if(S->top == -1){   //栈空
        return ERROR;
    }
    *e = S->data[S->top];   //记录栈顶元素
    return OK;
}

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

试末 微信支付

微信支付

试末 支付宝

支付宝