C/C++ 数据结构单链表的实现(初始化、插入、删除、销毁)
阅读原文时间:2023年07月09日阅读:9

#include
#include
#define MAX_SIZE 100
using namespace std;
//单链表
typedef struct _LinkList {
int data;//数据域
struct _LinkList* next;//指针域
}LNode,*LinkList;
//初始化单链表
bool InitLinkList(LinkList& L) {
L = new LNode;
if (!L) return false;
L->next = NULL;
return true;
}
//前插法
bool InsertList_front(LinkList& L, LNode *node) {
if (!L || !node) return false;
node->next = L->next;
L->next = node;
return true;
}
//尾插法
bool InsertList_back(LinkList& L, LNode* node) {
if (!L || !node) return false;
LNode* p = NULL;
p = L;
while (p->next){
p = p->next;
}
node->next = NULL;
p->next = node;
return true;
}
//在单链表的任意位置插入
bool InsertList_casual(LinkList& L, int i, LNode* node) {
if (!L || !node) return false;
int j = 0;
LNode* p = L;

while (p && j < i - 1) {  
    p = p->next;  
    j++;  
}  
if (!p||j>i-1) {  
    return false;  
}  
node->next = p->next;  
p->next = node;  
return true;  

}
//根据元素的位置获取元素
bool Get_Elems(LinkList& L,int i,LNode*& node) {
if (!L || !L->next)return false;
LNode* p = L->next;
int j = 1;
while (p && j < i) { p = p->next;
j++;
}
if (!p || j > i) return false;
node = p;
return true;
}
//按值查找元素
bool Find_Elme(LinkList& L,int &index,int elem) {
if (!L || !L->next)return false;
int j = 1;//位置的下标
LNode* p = L->next;
while (p&&p->data!=elem) {
p = p->next;
j++;
}
index = j;

if (!p )return false;

return true;  

}
//按元素的位置删除元素
bool Delete_Elem1(LinkList& L, int index, int &elem) {
if (!L || !L->next)return false;
LNode* p = L;
int j = 0;
while (p->next&&jnext;
j++;
}
if (!p->next || j > index - 1)return false;
LNode* q = NULL;
q = p->next;
elem = q->data;
p->next = q->next;
delete q;
return true;
}
//根据指定的元素删除元素
bool Delete_Elem2(LinkList& L,int elem) {
if (!L || !L->next)return false;
LNode* p = L;
while (p->next) {
if (p->next->data == elem) {
LNode* q = p->next;
p->next = q->next;
delete q;
//return true;
}
else {
p = p->next;
}
}
return true;
}
void DestroyList(LinkList& L) {
LNode* p;
p = L;
while (p) {
L = L->next;
cout << "删除元素: " << p->data << endl; delete p; p = L; } cout << "顺序表的销毁!" << endl; } void PrintList(LinkList& L) { LNode* p; p = L->next;
while (p) {
cout << p->data << " "; p = p->next;
}
cout << endl; } int main() { LNode* list = NULL; int count1 = 0;//前插法元素个数 int count2 = 0;//尾插法元素个数 int count3 = 0;//任意位置插入个数 int i = 0;//插入的位置 int e = 0;//要插入的元素 if (InitLinkList(list)) { cout << "单链表初始化成功!" << endl; } else { cout << "单链表初始化失败!" << endl; } PrintList(list); //前插法 cout << "请输入要插入的元素个数:(前插法)"; cin >> count1;
while (count1 > 0) {
LNode* p1 = NULL;
p1 = new LNode;
cout << "请输入要插入的元素:"; cin >> p1->data;
if (InsertList_front(list, p1)) {
cout << "元素 " << p1->data << " 插入成功!" << endl; } else { cout << "元素 " << p1->data << " 插入失败!" << endl; } count1--; } PrintList(list); //尾插法 cout << "请输入要插入的元素个数:(尾插法)"; cin >> count2;
while (count2 > 0) {
LNode* p2 = NULL;
p2 = new LNode;
cout << "请输入要插入的元素:"; cin >> p2->data;
if (InsertList_back(list, p2)) {
cout << "元素 " << p2->data << " 插入成功!" << endl; } else { cout << "元素 " << p2->data << " 插入失败!" << endl; } count2--; } PrintList(list); //在任意位置插入 cout << "请输入要插入的元素个数:(任意位置)"; cin >> count3;
while (count3 > 0) {
LNode* p3 = NULL;
p3 = new LNode;
cout << "请输入要插入的元素位置和元素:"; cin >> i >> p3->data;
if (InsertList_casual(list,i, p3)) {
cout << "元素 " << p3->data << " 插入成功!" << endl; } else { cout << "元素 " << p3->data << " 插入失败!" << endl; } count3--; } PrintList(list); //根据元素位置获取当前的值 LNode* p4 = NULL; cout << "请输入想要查找的元素位置:"; cin >> i;
if (Get_Elems(list, i, p4)) {
cout << "第 " << i << " 个元素是:" << p4->data << endl; } else { cout << "元素获取失败" << endl; } //按值查找元素 int elem = 0; int index = 0; cout << "请输入要查找的元素:"; cin >> elem;
if (Find_Elme(list,index, elem)) {
cout << "元素 " << elem << " 查找成功!" << "在单链表的第 " << index << " 个位置。" << endl; } else { cout << "元素查找失败!" << endl; } //按元素的位置删除元素 int element = 0;//要删除的元素 cout << "请输入要删除的元素的位置:"; cin >> i;
if (Delete_Elem1(list, i,element)) {
cout << "在 " << i << " 处的元素 " << element << " 删除成功!" << endl; PrintList(list); } else { cout << "元素删除失败!" << endl; } //按元素删除元素 int element2 = 0; cout << "请输入要删除的元素:"; cin >> element2;
if (Delete_Elem2(list,element2)) {
cout << "元素 " << element2 << " 删除成功!" << endl;
PrintList(list);
}
else {
cout << "元素删除失败!" << endl;
}
DestroyList(list);

system("pause");  
return 0;  

}