数据结构之线性表(顺序表,单链表,循环链表,双向链表)-- 图书管理系统

顺序表

#include <iostream>
#include <cstring>
#include <cstdlib>///exit()头文件exit(0):正常执行程序并退出程序。exit(1):非正常执行导致退出程序
#include <fstream>///fstream是C++ STL中对文件操作的合集
#include <iomanip>///c++ cin,cout格式化输入输出
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
const int MAXSIZE = 110;

struct Book
{
    string id;///编号
    string name;///书名
    double price;///定价
};
struct SqList
{
    Book *elem;///存储空间的基地址
    int length;///当前长度
};
Status InitList_Sq(SqList &L)///顺序表的初始化
{
    ///构造一个空的顺序表L;
    L.elem = new Book[MAXSIZE];///为顺序表分配一个大小为MAXNSIZE的数组空间
    if(!L.elem) exit(OVERFLOW);
    L.length = 0;
    return OK;
}
Status GetElem(SqList L, int i, Book &e)///顺序表的取值
{
    if(i<1 || i>L.length) return ERROR;///判断i值是否合理,若不合理,则返回ERROR
    e = L.elem[i-1];///elem[i-1]单元存储第i个数据元素
    return OK;
}
int LocateElem_Sq(SqList L, double e)
{
    for(int i=0; i<L.length; i++)
    {
        if(L.elem[i].price==e) return i+1;///查找成功,返回序号i+1
    }
    return 0;///未查找到,返回0
}
Status ListInsert_Sq(SqList &L, int i, Book e)///顺序表的插入
{
    ///在顺序表的第i个位置插入新的元素 i值的合法范围: 1<=i<=L.length+1
    if(i<1 || i>L.length+1) return ERROR;
    if(L.length==MAXSIZE) return ERROR;///当前存储空间已满
    for(int j=L.length-1; j>=i-1; j--)
    {
        L.elem[j+1] = L.elem[j];///插入位置及其之后的元素向后移动一个位置
    }
    L.elem[i-1] = e;///将新元素放入第i个位置(下标为i-1)
    ++L.length;///表长加1
    return OK;
}
Status ListDelete_Sq(SqList &L, int i)///顺序表的删除
{
    ///在顺序表中删除第i个位置的数据
    if(i<1 || i>L.length) return ERROR;///i值不合法
    for(int j=i; j<L.length; j++)
    {
        L.elem[j-1] = L.elem[j];///被删除之后的元素前移一个单位
    }
    --L.length;///表长减1
    return OK;
}
int main()
{
    SqList L;
    int i=0, temp, a, c, choose;
    double price;
    Book e;///定义一个Book类型的结构体
    string head_1, head_2, head_3;
    cout << "1. 建立\n";
	cout << "2. 输入\n";
	cout << "3. 取值\n";
	cout << "4. 查找\n";
	cout << "5. 插入\n";
	cout << "6. 删除\n";
	cout << "7. 输出\n";
	cout << "0. 退出\n\n";
	choose = -1;
	while(choose!=0)
    {
        cout<< "请选择:";
        cin>> choose;
        switch(choose)
        {
            case 1:
            {
                if(InitList_Sq(L)) cout<< "成功建立顺序表\n\n";
                else cout<< "顺序表建立失败\n\n";
            }
            break;
            case 2:
            {
               i = 0;
               L.elem = new Book[MAXSIZE];
               if(!L.elem) exit(OVERFLOW);
               L.length = 0;
               fstream file;
               file.open("book.txt");
               if(!file)
               {
                   cout<< "错误!未找到文件" <<endl;
                   exit(OVERFLOW);
               }
               file>> head_1 >> head_2 >> head_3;///编号 书名 定价
               while(!file.eof())
               {
                   file>> L.elem[i].id >> L.elem[i].name >> L.elem[i].price;
                   i++;
               }
               cout<< "输入 book.txt 信息完毕\n\n";
               L.length = i;
               file.close();
            }
            break;
            case 3:///顺序表的取值
            {
                cout<< "请输入一个位置用来取值:\n";
                cin>>i;
                temp = GetElem(L,i,e);
                if(temp!=0)
                {
                    cout<< "查找成功\n";
                    cout<< "第" << i << "本图书的信息是:\n";
                    cout<< left << setw(15) << e.id << "\t"  ///在C++中,setw(int n)用来控制输出间隔。
                        << left << setw(50) << e.name << "\t"
                        << left << setw(5) << e.price << endl
                        << endl;
                }
                else cout<< "查找失败,位置超出范围!\n\n";
            }
            break;
            case 4: //顺序表的查找
            {
                cout<< "请输入所要查找价格:";
                cin>> price;
                temp = LocateElem_Sq(L, price);
                if(temp != 0)
                {
                    cout<< "查找成功\n";
                    cout<< "该价格对应的书名为:" << L.elem[temp - 1].name << endl << endl;
                }
                else cout << "查找失败!没有这个价格对应的书籍\n\n";
            }
			break;
            case 5: ///顺序表的插入
            {
                cout<< "请输入插入的位置和书本信息,包括:编号 书名 价格(用空格隔开):";
                cin>> a;
                cin>> e.id >> e.name >> e.price; //输入a和b,a代表插入的位置,b代表插入的数值(书本信息)
                if (ListInsert_Sq(L, a, e))  cout << "插入成功.\n\n";
                else cout << "插入失败.\n\n";
            }
			break;
		    case 6: //顺序表的删除
            {
                cout<< "请输入所要删除的书籍的位置:";
                cin>> c;
                if (ListDelete_Sq(L, c))    cout<< "删除成功.\n\n";
                else cout<< "删除失败.\n\n";
            }
            break;
            case 7: ///顺序表的输出
            {
                cout<< "当前图书系统信息(顺序表)读出:\n";
			    for(i = 0; i < L.length; i++)
				cout<< left << setw(15) << L.elem[i].id << "\t"
                    << left << setw(50) << L.elem[i].name << "\t"
                    << left << setw(5) << L.elem[i].price << endl;
                cout << endl;
            }break;
		}
    }
    return 0;
}

这个代码是用到了文件操作的,所以需要在该cpp文件所在的文件夹里建一个book.txt存储一些数据信息,才能执行操作。

举个例子:给定以下数据信息

ISBN                              书名                                   定价
9787302257646            程序设计基础                    25
9787302219972            单片机技术及应用             32
9787302203513            编译原理                           46
9787811234923            汇编语言程序设计教程      21
9787512100831            计算机操作系统                17
9787302265436            计算机导论实验指导         18
9787302180630            实用数据结构                    29
9787302225065            数据结构(C语言版)       38
9787302171676           C#面向对象程序设计         39
9787302250692           C语言程序设计                  42
9787302150664           数据库原理                        35 
9787302260806           Java编程与实践                 56
9787302252887           Java程序设计与应用教程   39
9787302198505           嵌入式操作系统及编程       25
9787302169666           软件测试                            24
9787811231557           Eclipse基础与应用             35

 运行结果:

单链表

#include<iostream>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<fstream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;

struct Book
{
    string id;///编号
    string name;///书名
    double price;///定价
};
typedef Book ElemType;///ElemType仅仅代表数据类型
typedef struct LNode
{
    ElemType data;///节点的数据域
    struct LNode *next;///节点的指针域
}LNode, *LinkList;///LinkList为指向结构体LNode的指针类型(Linklist p == LNode *p,结构体指针)

Status InitList_L(LinkList &L)///构造一个空的单链表L
{
    L=new LNode;///生成新结点作为头结点,用头指针L指向头结点
    L->next=NULL;///头结点的指针于置空
    return OK;
}
Status GetElem_L(LinkList L, int i, Book &e)///单链表的取值,用e返回L中第i个数据元素的值(复杂度O(n))
{
    int j;///用j做计数器初值为1
    LinkList p;
    p=L->next;///用指针p指向首元结点
    j=1;
    while(j<i && p)///只要当前结点的指针p不为空(NULL),并且没有到达序号为i的结点,则继续循环
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i) return ERROR;///如果指针p为空(即:i>表长) 或者 计数器j>i,说明i<=0
    e=p->data;///取第i个结点的数据域
    return OK;
}

LNode *LocateElem_L(LinkList L, int e)///单链表的按值查找(时间复杂度O(n))(指针函数:返回值是一个指针)
{///在带头结点的单链表L中查找值为e的元素
    LinkList p;
    p = L->next;///初始化,P指向首元结点
    while(p && p->data.price!=e)///顺链域向后扫描,直到p为空或p所指的数据域等于e
    {
        p=p->next;///p指向下一个结点
    }
    return p;///查找成功返回值为e的结点地址p,查找失败返回NULL
}

Status ListInsert_L(LinkList &L, int i, Book &e)///单链表的插入
{///将值为e的新结点插入到表的第i个结点的位置上,即插入到a[i-1]与a[i]之间
    int j;
    LinkList p, s;
    p = L;
    j = 0;
    while(p && (j<i-1))///查找第i-1个结点,p
    {
        p = p->next;///(当j=0,p指向第一个结点,即当j=i-1,p指向第i个结点)
        ++j;
    }
    if (!p || (j>i-1)) return ERROR;///i>n+1 或者 i<1
    s = new LNode;///生成新结点*s
    s->data = e;///将结点*s的数据域置为e
    s->next = p->next;///将结点*s的指针域指向结点a[i]
    p->next = s;///将结点*p的指针域指向结点*s
    return OK;
}
Status ListDelete_L(LinkList &L, int i)///单链表的删除
{///在带头结点的单链表中,删除第i个元素
    LinkList p, q;
    int j;
    p = L;
    j = 0;
    while((p->next)&&(j < i - 1))///查找a[i-1]结点,并由指针p指向该结点
    {
      p=p->next;
      ++j;
    }
    if (!(p->next)||(j>i-1)) return ERROR;///当i>n 或 i<1时,删除位置不合理
    q = p->next;///临时保存被删结点i的地址以备释放
    p->next = q->next;///改变删除结点的前驱结点的指针域
    delete q;///释放删除结点的空间
    return OK;
}
int main()
{
    int a,n,choose;
    double price;
    Book e;
    LinkList L,p;
    string head_1, head_2, head_3;
    cout<<"1. 建立\n";
    cout<<"2. 输入\n";
    cout<<"3. 取值\n";
    cout<<"4. 查找\n";
    cout<<"5. 插入\n";
    cout<<"6. 删除\n";
    cout<<"7. 输出\n";
    cout<<"0. 退出\n\n";

    choose = -1;
    while(choose != 0)
    {
        cout<< "请选择:";
        cin>> choose;
        switch(choose)
        {
            case 1:///建立
            {
                if (InitList_L(L)) cout<<"成功建立链表!\n\n";
            }
            break;
            case 2:///前插法创建单链表
            {///前插法是通过将新结点逐个插入到链表的头部(头结点之后)来创建链表,每次申请一个新结点
             ///读入相应的数据元素值,然后将新结点插入到头结点之后
                L = new LNode;
                L->next = NULL;///建立一个带头结点的空链表
                int length = 0;
                fstream file;
                file.open("book.txt");
                if (!file)
                {
                    cout << "未找到相关文件,无法打开!" << endl;
                    exit(ERROR);
                }
                file >> head_1 >> head_2 >> head_3;
                while(!file.eof())///处理到文件结束
                {
                    p = new LNode;///生成新结点*p
                    file>> p->data.id >> p->data.name >> p->data.price;///将数据赋值给新结点*p的数据域
                    p->next = L->next;
                    L->next = p;///将新结点*p插入到头结点之后
                    length++;///表长加1
                }
                cout<< "输入 book.txt 信息完毕\n\n";
                file.close();
            }
            break;
            case 3:///单链表的序号取值
            {
                cout<<"请输入一个位置用来查找:";
                cin >>a;
                if(GetElem_L(L,a,e))
                {
                    cout<<"查找成功\n";
                    cout<<"第"<<a<<"本图书的信息是:\n";
                    cout<< left << setw(15) << e.id << "\t"
                        << left << setw(50) << e.name << "\t"
                        << left << setw(5) << e.price << endl << endl;
                }
                else cout<<"查找失败\n\n";
            }
            break;
            case 4:///单链表的按值查找
            {
                cout<<"请输入所要查找的价格:";
                cin >> price;
                if(LocateElem_L(L, price)!=NULL)
                {
                    cout<< "查找成功\n" ;
                    cout<< "该价格对应的书名:" << LocateElem_L(L, price)->data.name << endl << endl;
                }
                else cout<<"查找失败!定价"<<price<<" 没有找到\n\n";
            }
            break;
            case 5:///单链表的插入
            {
                cout<< "请输入插入的位置和书的信息,包括:编号 书名 价格(用空格隔开):";
                cin>>a;
                cin>> e.id >> e.name >> e.price;
                if(ListInsert_L(L,a,e))   cout<<"插入成功.\n\n";
                else  cout<<"插入失败!\n\n";
            }
            break;
            case 6:///单链表的删除
            {
                cout<<"请输入所要删除的书籍位置:";
                cin >>a;
                if(ListDelete_L(L, a))   cout<<"删除成功!\n\n";
                else  cout<<"删除失败!\n\n";
            }
            break;
            case 7:///单链表的输出
            {
                cout << "当前图书系统信息(链表)读出:\n";
                p=L->next;
                while(p)
                {
                    cout<< left << setw(15) << p->data.id << "\t"
                        << left << setw(50) << p->data.name << "\t"
                        << left << setw(5) << p->data.price <<endl;
                    p=p->next;
                }
                cout<<endl;
            }
            break;
        }
    }
    return 0;
}

还用上面的那组数据吧!

循环链表

循环链表特点:最后一个结点的指针域指向头结点,整个链表形成一个环。循环链表和单链表的操作基本一致,唯一的差别就是:遍历链表的时候,判断当前指针p是否指向表尾结点的终止条件不同。在单链表中,判别条件为p!=NULL 或 p->next!=NULL,而在循环单链表的判断条件为p!=L 或 p->next!=L。

循环链表的合并问题:(对设置有头指针和尾指针的两个循环链表)①:第二个表的尾指针指向第一个表的头结点。②:将第一个表的尾指针指向第二个表的第一个结点。③:然后释放第二个表的头结点。 

p = B->next->next;/// p为第二个链表的第一个结点的地址
B->next = A->next;///将第二个表的尾指针 指向 第一个表的 头结点
A->next = p;///将第一个结点的尾指针 指向 第二个表的第一个结点
A B 分别为两个链表的尾地址

双向链表

 在双向链表的节点中有两个指针域,一个指向直接后继,一个指向直接前驱。

和上面的单链表类似,可以试着比较学习。

#include <bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR 0
typedef int Status;

struct Book
{
    string id;
    string name;
    double price;
};
typedef Book ElemType;
typedef struct DuLNode
{
    ElemType data; ///数据域
    struct DuLNode *prior;///指向直接前驱
    struct DuLNode *next;///指向直接后继
}DuLNode,*DuLinkList;

Status InitList_L(DuLinkList &L)
{
    L = new DuLNode;
    L->prior = NULL;
    L->next = NULL;
    return OK;
}

DuLNode *GetElem_DuL(DuLinkList L, int i)///指针函数,返回一个DuLNode的地址。该函数返回第i个位置的地址
{
    DuLinkList p, s;
    p = L;
    int cnt = 0;
    while(cnt<i && p)
    {
        p = p->next;
        s = p;
        cnt++;
    }
    return s;
}
Status List_Insert(DuLinkList &L, int i, ElemType e)///双向链表的插入
{///在带有头结点的双向链表L中的第i个位置之前插入元素e
    DuLinkList p, s;
    if(!(p = GetElem_DuL(L,i))) return ERROR;///在L中确定第i个元素的位置指针p,p为NULL时,第i个元素不存在
    s = new DuLNode;///生成新结点*s;
    s->data = e;///将结点*s的数据域为e
    s->prior = p->prior;///先将s的前驱指向第i-1个结点
    p->prior->next = s;///将i-1个结点的后驱指向s
    s->next = p;///将s的后驱指向第i个结点
    p->prior = s;///将第i个结点的前驱指向s
    return OK;
}
Status ListDelete_DuL(DuLinkList &L, int i)///双向链表的删除
{///删除带头结点的双向链表中的第i个元素
    DuLinkList p;
    if(!(p = GetElem_DuL(L,i))) return ERROR;///在L中确定第i个元素的位置指针p,p为NULL时,第i个元素不存在
    p->prior->next = p->next;///将第i-1个结点的前驱 指向 第i+1个结点
    p->next->prior = p->prior;///将第i+1个结点的前驱 指向 第i-1个结点
    delete p;///释放被删结点的空间
    return OK;
}
int main()
{
    int a, n, choose;
    DuLinkList L, p;
    Book e;
    string head_1, head_2, head_3;
    cout<<"1. 建立\n";
    cout<<"2. 输入\n";
    cout<<"3. 插入\n";
    cout<<"4. 删除\n";
    cout<<"5. 输出\n";
    cout<<"0. 退出\n\n";

    choose = -1;
    while(choose != 0)
    {
        cout<< "请选择:";
        cin>>choose;
        switch(choose)
        {
            case 1:
            {
                if(InitList_L(L)) cout<<"成功建立链表!\n\n";
            }
            break;
            case 2:
            {
                DuLinkList r;
                L = new DuLNode;
                L->prior = NULL;
                L->next = NULL;
                r = L;
                fstream file;
                file.open("book.txt");
                if(!file)
                {
                    cout<< "未找到相关文件,无法打开!" << endl;
                    exit(ERROR);
                }
                file>> head_1 >> head_2 >> head_3;
                while(!file.eof())///使用后插法创建双向链表(通过尾指针r)
                {
                    p = new DuLNode;///生成新结点*p
                    file>> p->data.id >> p->data.name >> p->data.price;
                    r->next = p;
                    p->prior = r;
                    p->next = NULL;
                    r = p;
                }
                cout<< "输入 book.txt 信息完毕\n\n";
                file.close();
            }
            break;
            case 3:
            {
                cout<< "请输入插入的位置和书的信息:包括:编号 书名 价格(用空格分开):";
                cin>> a;
                cin>> e.id >> e.name >> e.price;
                if(List_Insert(L, a, e)) cout<< "插入成功.\n\n";
                else cout<<"插入失败!\n\n";
            }
            break;
            case 4:
            {
                cout<< "请输入要删除的书籍位置:";
                cin>> a;
                if(ListDelete_DuL(L, a)) cout<< "删除成功!\n";
                else cout<< "删除失败!\n\n";
            }
            break;
            case 5:
            {
                cout<< "当前图书系统信息(链表)读出:\n";
                p = L->next;
                while(p)
                {
                    cout<< left << setw(15) << p->data.id << "\t"
                        << left << setw(50) << p->data.name << "\t"
                        << left << setw(5) << p->data.price << endl;
                    p = p->next;
                }
                cout<< endl;
            }
            break;
        }
    }
    return 0;
}

运行结果: 

原文链接:加载失败,请重新获取