设计题目—单向链表

已知技术参数和设计要求
1、主要参数：空头链表、表头
2、完成以下的操作：插入链表项、追加链表项、连接两个链表、将个链表项逆向输出、返回链表的数据项数、输出一个已生成的链表。
3、要应用以下知识点：类的定义、对象的定义、构造函数及其重载、友员类、使用new动态创建对象。
设计内容与步骤
1、定义链表为一个类
2、分析设计所有的操作
3、程序设计、实现、调试
4、课程设计说明书

头文件：LinkList.h

typedef struct LNode {
int data;
struct LNode *next;
}LNode, *pLinkList;

class LinkList {
private:
pLinkList m_pList;
int m_listLength;
public:
LinkList();
~LinkList();
bool InitList ();
bool DestroyList ();
bool ClearList();
bool IsEmpty ();
int GetLength ();
bool GetNode(int position, LNode** node);
int LocateElem(int elem);
bool SetNodeData(int position, int newData);
bool GetNodeData(int position, int &data);
bool InsertNode(int beforeWhich, int data);
bool DeleteNode(int position);
};

Cpp文件：LinkList.cpp

#include
#include "LinkList.h"

LinkList::LinkList() {
m_pList = NULL;
m_listLength = 0;

InitList();
}

LinkList::~LinkList() {
if (!DestroyList()) {
DestroyList();
}
}

//初始化，分配一个头节点。
bool LinkList::InitList() {
if (!(m_pList = new LNode)) {
return false;
}
m_pList->next = NULL;

return true;
}

//销毁链表。
bool LinkList::DestroyList() {
if (!ClearList()) {
return false;
}

delete m_pList;

return true;
}

//判断链表是否为空。若为空，返回true，否则返回false。
bool LinkList::IsEmpty() {
if (m_pList->next == NULL) {
return true;
}
return false;
}

//返回链表的中当前节点数。
int LinkList::GetLength() {
return m_listLength;
}

//将链表清空，释放当前所有节点。
bool LinkList::ClearList() {
if (m_pList == NULL) {
return false;
}

LNode *pTemp = NULL;
while (m_pList->next != NULL) {
pTemp = m_pList->next;
m_pList->next = pTemp->next;
delete pTemp;
}
m_listLength = 0;

return true;
}

//将position指定的节点内的数据设置为newData。
//第一个有效节点的position为1。
bool LinkList::SetNodeData(int position, int newData) {
LNode *pTemp = NULL;

if (!(GetNode(position, &pTemp))) {
return false;
}

pTemp->data = newData;

return true;
}

//得到指定位置节点的数据。
//节点索引从1到listLength。
bool LinkList::GetNodeData(int position, int &data) {
LNode *pTemp = NULL;

if (!(GetNode(position, &pTemp))) {
return false;
}

data = pTemp->data;

return true;
}

//在链表中插入一个节点。
//插入的位置由beforeWhich指定，新节点插入在beforeWhich之前。
//beforeWhich的取值在1到ListLength+1之间。
bool LinkList::InsertNode(int beforeWhich, int data) {
LNode *pTemp = NULL;

if (beforeWhich < 1 || beforeWhich > (m_listLength + 1)) {
return false;
}

if (!(GetNode(beforeWhich - 1, &pTemp))) {
return false;
}

LNode *newNode = new LNode;
newNode->data = data;
newNode->next = pTemp->next;
pTemp->next = newNode;

m_listLength++;

return true;
}

//删除一个指定的节点。
//节点位置由position指定。
//positon的值从1到listLength。
//若链表为空或指定的节点不存在则返回false。
bool LinkList::DeleteNode(int position) {
if (position < 1 || position > m_listLength) {
return false;
}

LNode *pTemp = NULL;
if (!(GetNode(position - 1, &pTemp))) {
return false;
}

LNode *pDel = NULL;
pDel = pTemp->next;
pTemp->next = pDel->next;
delete pDel;

m_listLength--;

return true;
}

//得到指定位置节点的指针。
bool LinkList::GetNode(int position, LNode **node) {
LNode *pTemp = NULL;
int curPos = -1;

pTemp = m_pList;
while (pTemp != NULL) {
curPos++;
if (curPos == position)
break;
pTemp = pTemp->next;
}

if (curPos != position) {
return false;
}

*node = pTemp;

return true;
}

//定位与指定数据相等的数据节点。
//如果在当前链表中已经存在该数据则返回该数据节点的索引号。
//若不存在这样的节点则返回0。
//节点索引从0开始到listLength。
int LinkList::LocateElem(int elem) {
LNode *pTemp = NULL;
int curIndex = 1;

pTemp = m_pList->next;
while ((pTemp != NULL) && (pTemp->data != elem)) {
pTemp = pTemp->next;
curIndex++;
}

if (pTemp == NULL) {
return 0;
}

return curIndex;
}

#include "stdafx.h" #include #include #include #include typedef struct element { int data; } element; typedef struct linknode { element elem; struct linknode *next; } linknode, *linklist; enum ordertype { ascending, descending }; void init(linklist *list) { *list = (linklist )malloc(sizeof(linknode)); if (*list == null) { printf("分配链头失败，退出。。\n"); exit(1); } memset(*list, 0, sizeof(linknode)); } int insert(linklist list, int data) { if (list == null) return 0; linklist p = (linklist )malloc(sizeof(linknode)); if (p == null) return 0; p->elem.data = data; p->next = list->next; list->next = p; return 1; } void cleanup(linklist list) { linklist p = list; while (p) { list = list->next; free(p); p = list; } } void display(linklist list) { linklist cursor = list->next; while (cursor) { printf("%d ", cursor->elem.data); cursor = cursor->next; } } int get(linklist list, int n, int *data) { linklist cursor = list->next; int i = 0; while ((cursor != null) && (i < n)) cursor = cursor->next; if (cursor != null) { *data = cursor->elem.data; return 1; } return 0; } linklist sortlist(linklist head, ordertype order) { linklist cursor, first, tail, prev, max; first = null; while (head != null) { for (cursor = max = head; cursor->next != null; cursor = cursor->next) { if (order == descending && cursor->next->elem.data > max->elem.data) { prev = cursor; max = cursor->next; } else if (order == ascending && cursor->next->elem.data < max->elem.data) { prev = cursor; max = cursor->next; } } if (first == null) first = tail = max; else tail = tail->next = max; if (max == head) head = head->next; else prev->next = max->next; } if (first != null) { tail->next = null; } return first; } void main() { linklist head; init(&head); int data; printf("请输入链表节点值(0结束输入)：\n"); scanf("%d", &data); while (data) { insert(head, data); scanf("%d", &data); } printf("请输入排序方法：1. 升序 2. 降序\n"); scanf("%d", &data); if (data == 1) head->next = sortlist(head->next, ascending); else if (data == 2) head->next = sortlist(head->next, descending); display(head); cleanup(head); system("pause"); }

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息