线性表的链式存储结构基本实现（C++）-白红宇

线性表的链式存储结构基本实现（C++）

阅读量：4050 次

发布时间：2019-05-25

本文共 3831 字，大约阅读时间需要 12 分钟。

原理一看都懂，代码一看就会，自己一写就错。花了将近3个小时才完成这个代码。有时候真的会自我怀疑，希望坚持下去的结果能让自己满意。

线性表的链式存储结构基本实现，先上代码（如下功能函数）：

这次我将链表中的数据定义为一个class对象，其中包含了书的名字，价格和折扣情况。

bool GetElem(const LinkList &L, int i, Book &out) //获得链表第i个的数据放到out中void CreateListHead(LinkList &L, int n) //头插法初始化链表void CreateListTail(LinkList &L, int n) //尾插法初始化链表void Show(LinkList & L)   //显示链表中所有元素bool ListInsert(LinkList & L, int i, Book e)   //在链表第i个位置中插入数据ebool ListDelete(LinkList &L, int i, Book &e)   //删除链表第i个位置的元素，并将删除对象放在e中void ClearList(LinkList &L)   //清空链表

需要注意的几个问题：

1、线性链表的定义是从1开始的，本代码中默认了0开始，以后再改吧；2、链式存储结构在插入数据时，有一个新建Node过程，即分配空间。因此在删除Node时不能忘记释放过程（free）;3、注意头指针和头结点的区别，并且在传递头指针参数时，要使用引用方法；

线性表的链式存储结构头文件

#pragma once#ifndef LINEARLIST_H_#define LINEARLIST_H_#include
   
    using namespace std;class Book{
   private:	string bookname;	double price;	double discount;public:	Book() {
   }	Book(string bn, double pr, double di) :		bookname(bn), price(pr), discount(di) {
   }	string &BookName() {
    return bookname; }	double Price() {
    return price; }	double Discount() {
    return discount; }};struct Node{
   	Book data;	struct Node *next;};typedef struct Node *LinkList;bool GetElem(const LinkList &L, int i, Book &out){
   	LinkList p = L->next;	while (p) {
   		if (i == 0) {
   			out = p->data;			return true;		}		p = p->next;		i--;	}	return false;}void CreateListHead(LinkList &L, int n){
   	L = new Node;	L->next = NULL;	for (int i = 0; i < n; i++) {
   		LinkList p = new Node;		cout << "Enter book name: ";		string name;		getline(cin, name);		cout << "Enter book price: ";		double pri;		cin >> pri;		cout << "Enter book discount: ";		double dis;		cin >> dis;		while (cin.get() != '\n')			continue;		p->data = {
    name,pri,dis };		p->next = L->next;		L->next = p;	}}void CreateListTail(LinkList &L, int n){
   	L = new Node;	L->next = NULL;	LinkList r;	r = L;	for (int i = 0; i < n; i++) {
   		LinkList p = new Node;		cout << "Enter book name: ";		string name;		getline(cin, name);		cout << "Enter book price: ";		double pri;		cin >> pri;		cout << "Enter book discount: ";		double dis;		cin >> dis;		while (cin.get() != '\n')			continue;		p->data = {
    name,pri,dis };		r->next = p;		r = p;	}	r->next = NULL;}void Show(LinkList & L){
   	LinkList p = L->next;	int i = 1;	while (p) {
   		cout << "Book " << i << " name: " << p->data.BookName() << endl;		cout << "Book " << i << " price: " << p->data.Price() << endl;		cout << "Book " << i << " discount: " << p->data.Discount() << endl;		i++;		p = p->next;	}}bool ListInsert(LinkList & L, int i, Book e){
   	LinkList p = L;	while (p) {
   		if (i == 0) {
   			LinkList s = new Node;			s->data = e;			s->next = p->next;			p->next = s;			return true;		}		p = p->next;		i--;	}	return false;}bool ListDelete(LinkList &L, int i, Book &e){
   	LinkList p = L;	while (p) {
   		if (i == 0) {
   			LinkList q = p->next;			p->next = q->next;			e = q->data;			free(q);			return true;		}		p = p->next;		i--;	}	return false;}void ClearList(LinkList &L){
   	LinkList p = L, q;	while (p) {
   		q = p->next;		free(p);		p = q;	}	L->next = NULL;}#endif // !LINEARLIST

线性表的链式存储结构使用示例

#include
   
    #include"linearlist.h"#include
    
     #include
     
      using namespace std;void main(){
   	LinkList test1;	CreateListHead(test1, 2);	cout << "\nYour data is: " << endl;	Show(test1);	if (ListInsert(test1, 1, {
    "BOOK THIEF",66.3,0.8 })) {
   		cout << "\nAfter insert a data: " << endl;		Show(test1);	}	Book out;	if (GetElem(test1, 1, out)) {
   		cout << "\nGet data : " << endl;		cout << "Book name: " << out.BookName() << endl;		cout << "Book price: " << out.Price() << endl;		cout << "Book discount: " << out.Discount() << endl;	}	if (ListDelete(test1, 1, out)) {
   		cout << "\nAfter delete a data: " << endl;		Show(test1);	}	ClearList(test1);	cout << "\nAfter clear list: " << endl;	Show(test1);}