当前位置： 首页 > news >正文

服务网站策划书网络营销咨询公司

news 2025/7/7 21:38:18
服务网站策划书,网络营销咨询公司,做网站登录的需求分析,网站建站建设价格目录 例1 矩阵相乘 线性表 2.1 线性表的类型定义 例2-1 求并集 LALA∪LB 例2-2 有序表归并 2. 2 线性表的顺序表示和实现 1．构造空表 2．插入 3．删除 4．定位 顺序表的优点： 顺序表的缺点： 例…

目录

例1 矩阵相乘

线性表

2.1   线性表的类型定义

例2-1 求并集  LA=LA∪LB

例2-2 有序表归并

2. 2  线性表的顺序表示和实现

1．构造空表

2．插入

3．删除

4．定位

顺序表的优点：

顺序表的缺点：

例：交替扫描

2. 3  线性表的链式表示和实现

绪论

例1 矩阵相乘

两个方阵相乘Cn×n=An×n × Bn×n

for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {c[i][j] = 0;//把新矩阵中的每个数初始化为0，方便后续计算新矩阵每位的值for (k = 0; k < n; k++) {c[i][j] = c[i][j] + a[i][k] * b[k][j];//每次计算第i行第k位上的数和第j列第k位上的数的乘积并进行累加，得到新矩阵中第i行第j列上的数}}
}

线性表

2.1   线性表的类型定义

基本操作效果
InitList（&L）初始化线性表，将线性表设置为初始状态（比如长度置为 0 等）
DestroyList（&L）销毁线性表，释放线性表占用的内存空间等相关资源
ClearList（&L）置空表，也就是清除表中已有的元素，使表的长度变为 0，但保留线性表结构本身，以便后续继续使用
ListEmpty（L）判空表，判断线性表是否为空，若为空返回真（通常用 1 表示），否则返回假（通常用 0 表示）
ListLength（L）求表长，返回线性表中当前所包含元素的个数
GetElem（L，i，&e）取第 i 个元素，将线性表 L 中第 i 个位置的元素值赋给变量 e（通过传址 &e）
LocateElem（L，e，compare（））查找元素，根据给定的比较函数 compare，在线性表 L 中查找和元素 e 满足比较条件的元素位置（比如相等时的首次出现位置等）
PriorElem（L，cur_e，&pre_e）求前驱元素，在线性表 L 中查找元素 cur_e 的前驱元素，并将其值赋给 pre_e（通过传址 &pre_e），如果 cur_e 无前驱则按约定进行相应返回（比如返回特殊值表示无前驱等）
NextElem（L，cur_e，&next_e）求后继元素，在线性表 L 中查找元素 cur_e 的后继元素，并将其值赋给 next_e（通过传址 &next_e），如果 cur_e 无后继则按约定进行相应返回（比如返回特殊值表示无后继等）
ListInsert（&L，i，e）插入元素，将元素 e 插入到线性表 L 的第 i 个位置，插入后线性表长度会相应增加
ListDelete（&L，i，&e）删除元素，删除线性表 L 中第 i 个位置的元素，并将被删除的元素值赋给 e（通过传址 &e），删除后线性表长度会相应减少
ListTraverse（L，visit（））按照 visit 函数定义的方式遍历表，对线性表中的每个元素依次执行 visit 函数指向的操作

例2-1 求并集  LA=LA∪LB

void union(List& La, List Lb)
{int La_len = ListLength(La);int Lb_len = ListLength(Lb);int e;for (int i = 0; i < Lb_len; i++){GetEleme(Lb, i, e);//把Lb中 i下标的元素放到变量e中if (!LocatList(La, e, equal))//如果La中没有找到和e相同的数ListInsert(La, ++La_len, e);//把e元素插入到La的最后，La的长度再自加}}

例2-2 有序表归并

void MergeList(List La, List Lb, List& Lc)
{InitList(Lc);int La_len = ListLength(La);int Lb_len = ListLength(Lb);int i, j, k = 0;while (i <= La_len && j <= Lb_len)//把La和Lb中较小的一个先放入Lc中{GetEleme(La, i, ai);GetEleme(LB, j, Bj);if (ai <= bj){ListInsert(Lc, ++k, ai);++i;}else {ListInsert(Lc, ++k, bj);++j;}}while (i <= La_len)//Lb已经遍历完，剩下La部分直接插入Lc{GetEleme(La, i, ai);ListInsert(Lc, ++k, ai);++i;}while (j <= Lb_len)//La已经遍历完，剩下Lb部分直接插入Lc{GetEleme(Lb, i, bj);ListInsert(Lc, ++k, bj);++j;}}

2. 2  线性表的顺序表示和实现

顺序表(Sequential List) ：用顺序存储的线性表，即把线性表的结点按逻辑次序依次存放到一组地址连续的存储单元里 

顺序表通过 元素的存储顺序 反映逻辑关系

1．构造空表

typedef int Elemtype;//把int类型重命名为Elemtype,想要修改类型时只需改此处
const int maxsize = 100;
typedef struct//定义了一个名字叫Sqlist1的数据结构
{Elemtype elem[maxsize];int length;
}Sqlist1;void InitList(Sqlist1* L)//初始化线性表
{l->length = 0;
}

2．插入

在表的第i（0≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表(a1,…,ai−1,ai,…,an)变为长度为n+l的线性表(a1,…,ai−1,x,ai,…,an)。

先将表中位置i～n上的结点全部后移一位以空出第i个位置，然后在该位置上插入新结点x，最后表长加1。  

注意：移动只能从后向前进行，即按n,n−1,…,i的次序进行。

int ListInsert(Sqlist* L, ElemType x, int i)//在顺序表L中的第i个位置插入x
{int j；if（L->n == maxsize）//判满{ cout << "表满，不能插入！（上溢）\n";//cout <<相当于print（），是打印的意思return -1; }if (i<0 || i> L->n + 1)//判位{cout << "非法插入位置\n"；return 0；}//插入操作for (j = L->n; j >= i; j--)L->elem[j] = L->elem[j - 1];//把i位置前的数后移L->elem[i - 1] = x;//插入x，第i个位置的下标是i-1L->n++;//表长加一return 1；//修改成功}

平均时间复杂度 

3．删除

将表的第i（1≤i≤n）个结点删去，使长度为n的线性表(a1,…,ai−1,ai,ai+1,…,an)变为长度为n−1的线性表(a1,…,ai−1,ai+1,…,an-1)。

先将表中位置i+1～n上的结点全部前移一位以填补删除操作造成的空缺。最后表长减1。 注意：移动只能从前向后进行，即按 i+1, i+2, …, n 的次序进行。

int ListDelete(Sqlist* L, int i)
{int j;if (L->length == 0)//判空cout << "表空，不能删除！（下溢）\n"；return -1；if (i<1 || i> L->n)//判合法删除cout << "非法删除位置！\n"；return 0；for (j = i + 1; j <= L->n; j++)//把i位置的后面的数依次前移，覆盖掉i位置的数L->elem[j - 2] = L->elem[j - 1];//为什么是L->elem[j-2] = L->elem[j-1];//“第i个位置”对应i-1下标，因为只有第一、二……个位置的说法（即i从1开始计数）,而下标是从0开始的//删掉“第i个位置”上的数，相当于用后一位数覆盖i位置上的数，后面剩下的数往前移 补空位//循环控制变量 j 需要从要删除元素位置的下一个【位置】开始，也就是 i + 1 开始，然后依次把 j 【位置】的元素往前移动一位，赋值给 j - 1 【位置】//因此j【位置】的数组【下标】是j-1，j-1【位置】的数组【下标】是j-2L->n--;//修改表长return 1;}

4．定位

求表L中第一个值为x的结点的序号，当不存在这种结点时结果为0。因此可从前向后比较各结点的值是否等于x。

int LocatElem(Sqlist* L, int x)
{int i；for (i = 1; i <= L->n；i++)if (elem[i - 1] == x) return i;//找到else return 0;//未找到
}

顺序表是线性表最简单的一种存储结构

顺序表的优点：

1  无需为表示逻辑关系而增加额外的存储空间(物理顺序可反映逻辑关系)；

2.可随机存取任一元素；i,    l.elem+  (i-1)sizeof(type)；p++;a[];

3.方法简单(各种高级语言都有数组类型)。

顺序表的缺点：

1.插入、删除会引起大量元素移动；

2.空间预(静态)分配，有浪费或不足问题。

例：交替扫描

已知顺序表结点值有正有负，使负值结点位于顺序表的前面部分，正值结点位于顺序表的后面部分。

方法1：对顺序表从前向后搜索（或称扫描），遇到正值结点就将它插入到表的后部（或从后向前搜索，遇到负值结点就将它插入到表的前部）。但顺序表上插入或删除不方便，要移动大量结点，效率不高。

方法2：由表的两端向中间交替扫描，即先从前向后扫描，找到一个值为正的结点，再从后向前扫描，找到一个值为负的结点，然后交换两者的内容。接着再从这两个位置开始继续进行同样的过程，直到两个扫描方向相遇，整个表扫描处理完毕。这样就避免了大量结点的移动问题。

void order(Sqlist *L)
{Elemtype x;
int i=0;
int j=L-> length-1;
while(i<j){while(i<j && L-> elem[i]<0) i++;//从前往后找正数while(i<j && L-> elem[j]>0) j--;//从后往前找负数if(i<j)//交换{ x= L-> elem[i];L-> elem[i] = L-> elem[j];L-> elem[j] = x;i++;j--;}}
}

2. 3  线性表的链式表示和实现

链表 (Linked List) ：用链式存储的线性表，即用一组任意的存储单元存储线性表的各个数据元素，相互间的逻辑关系(前趋或后继)通过附加指针表示；所有结点通过指针域链接在一起，构成一个链表。

  •  元素之间的逻辑关系通过附加指针表示；  
  • 结点可以连续，可以不连续；  
  • 结点的逻辑顺序与物理顺序可以不一致。

2.3.1  单链表

单链表(Singly Linked List)：每个结点有两部分信息：数据域，存放结点的值（内容）；指针域（亦称链域），存放结点后继的地址（或位置）。由于每个结点只有一个链域，故得名。

概念解释：

  • 空指针：不指向任何结点;
  • 头指针：单链表第一个结点的地址;
  •  单链表由头指针唯一确定；
  •  头指针具有标识单链表的作用；
  •  单链表常用头指针命名，如 head 表。
  • 头结点：单链表第一个结点前人为增加的结点，不存放数据。  作用：1、简化链表操作，统一空表与非空表  2、有时可将头结点看成0号结点

创建结点

typedef int ElemType;//给int类型起了一个别名ElemTypetypedef struct LNode{//结点中的两个成员变量
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//通过typedef为struct LNode结构体定义了两个别名
//一个是LNode（可以直接用来声明结构体变量，等同于使用struct LNode）
//另一个是*LinkList，LinkList通常用于表示指向链表头节点的指针类型LinkList head,p;// head 和 p 是两个指针变量，等价于LNode  *head ,  *p  ；

结点的动态分配与释放

//动态分配
p= new LNode;//方法一
p= (LinkList) malloc(sizeof(LNode));//方法二//malloc用于在堆内存中动态分配指定字节大小的内存空间
//它的参数sizeof(LNode) 计算了LNode 类型所占用的字节大小
//然后malloc 函数会在堆上找到一块对应大小的空闲内存块
//并返回指向这块内存起始地址的指针（该指针类型为void *，即无类型指针）
//由于需要将其赋值给LinkList 类型的指针p
//所以进行了强制类型转换(LinkList)//释放
delete p;//方法一
p=NULL;//方法二
free(p);//方法三

（1）插入(无头结点)

情况一：在空表上、首结点前插入

s= new LNode;//产生一个新节点
s->data = x;//把x赋到数值域中
s-> next = head;//把s和head（头结点）地址赋给s
head=s;//s就成了头结点

情况二：在中间结点、尾结点后插入

s=new LNode;
s->data = x;
s->next = p ->next;//先把后面的链子接上
p->next = s; //再链接前面的

注意指针修改顺序：先改变本身指针域，后改变指向本身的指针域。

（1）插入(有头结点)

情况一：插入到任意结点后

s = new LNode;
s -> data = x;
s-> next = p ->next;//先链接上后面
p->next = s;//再链接上前面

情况二：插入到第i结点前 

思路：

  1. 查找第 i-1个结点；
  2. 建立新结点；
  3. 修改第 i-1个结点和新结点的指针。

不需移动结点，只需修改有关指针 ；需从表头开始顺序查找插入位置

int insert(LinkList head, ElemType x, int i) {LinkList q, s;q = LocateElem(head, i - 1);//找到第i-1结点的地址if (q == 0) {//无第i-1位置的结点，即i<1 || i> (LinkList->length)cout << "非法插入位置！\n"；return 0；}s = new LNode;//生成新结点s->data = x;s->next = p->next;//新点的后继是原第i个点p->next = s; //原第i−1个点的后继是新点return 1;//插入成功
}

（1）等效插入（在*p之前 前插）

不用找前趋的前插 ：

  • 新结点插在当前点*p后
  • 交换两结点内容

逻辑上与原来在*p之前插入等效。

//正常把s节点插入，通过和前一个节点互换数值，从而在逻辑上实现“前插”
s= new LNode;
s->data = p->data;//把p中数值放到s中
s->next = p->next;//s链接后面的结点
p->next = s;//s链接前面的节点
p->data = x;//把s的值放入p中

（2）删除(无头结点)

情况一：删除首结点

 

p=head;//记录头结点
head=head->next;//把下一个结点设为头结点
delete p;//删除原头结点

情况二：删除中间结点、尾结点

q->next = p->next;
delete p;

（2） 删除(有头结点)

删除任意结点

q->next = p->next;
delete p;

（2）删除第i结点(等效删除)

思路：

  • 查找链表的第 i-1个结点，设q指向它， p指向第i个结点；
  • 修改第 i-1个结点的后继指针，使其指向第i个结点的后继；
  • 释放第i个结点空间；
int delete(LinkList head, int i) {LinkList p, q;q = LoacteElem(head, i - 1);//找待删点的前驱if (q == NULL || q->next == NULL) {cout << "非法删除位置！\n"；return 0;}p = q->next;//保存一份待删点的地址q->next = p->next;//修改前趋的后继指针delete p;//释放结点return 1;//删除成功}

(3) 建表(头插法)

  • 从空表开始，反复读入数据:
  1.  生成新结点
  2. 将读入数据存放到新结点的数据域中
  3. 将该新结点插入到链表的前端
  • 直到读入结束符为止。

LinkList create() {//创造头结点LinkList head, s;char ch;head = new LNode;//创造头结点while (cin >> ch, ch != '$') {s = new LNode;//创造结点s->next = head->next;s->data = ch;head->next = s;}return head;
}

 (3)建表(尾插法)

  • 从空表开始，反复读入数据：
  1. 生成新结点
  2. 将读入数据存放到新结点的数据域中
  3. 将该新结点插入到链表的尾端
  • 直到读入结束符为止。

LinkList create()//尾插法建表，有头结点
{LinkList head, rear, s;char ch;head = new LNode;//生成头结点（说明是空表）rear = head;//第一个结点既是头结点也是尾结点while (cin >> ch, ch != '$')//这是一个逗号表达式，最后一条语句的结果就是（）的结果，cin>>类似scanf（），把键盘输入的值传入变量ch中{s = new LNode;s->data = ch;//生成新节点rear->next = s;rear = s;//用rear标识尾结点}raer->next = NULL;//尾结点的后继为空return head；//链表的头结点可以标识一整个链表
}

 (4)初始化

建立一个只有头结点的空表

LinkList initlist()
{ LinkList head;head=new Lnode;head−>next=NULL;return head;
}

(5)求表长

int ListLength_L(LinkList L)
{int j = 0;LinkList p;p = L->next;//从首结点开始//从首结点开始是 p = L->next 而不是 p = L 的原因:
//在常见的链表实现中（尤其是带头结点的链表），头结点主要起到一个 “标识” 作用
//它本身通常并不存放实际要处理的数据元素
其 next 指针才指向链表中的第一个真正存有有效数据的节点，也就是首结点。while(p !=NULL)//逐点检测、计数{j++;p = p->next;}return j;
}

(6)按值查找

LinkList LocateElem_L(LinkList L, ElemType x)
{LinkList p;p = L->next;//从首结点开始搜索 注意！不是头结点！是首结点！while (p != NULL){if (p->data == x) return p;//找到了，立即终止函数，并返回查找节点的地址p = p->next;//没找到，继续找}return NULL;//P==NULL了都没找到
}

注意：返回结点号,头结点视为0号

(7)按序号查找(定位)

LinkList GetElem_L(LinkList L, int i)
{int j;LinkList p;if (i<0 || i> L->length) {cout << "位置非法，无此结点\n"；return NULL;}j = -1;p = head;while (p != NULL){j++;if (j == i) break;p = p->next;}return p
}
//为什么j要从−1开始//一般情况下，链表的节点位置计数是从 1 开始//指针p是从链表的头结点开始搜索的,然而头结点本身在实际数据节点计数时不算在内，算作0位置//进入while循环时，先j++,刚好j为0，标识0位置的头结点//当p第一次移动时，再变为 1，正好和实际数据节点从 1 开始计数的方式相对应

例  单链表求和

ElemType sum(LinkList L)
{LinkList p = L->next;ElemType sum = 0;while (p != NULL){sum += p->data;p = p->next;}return sum;}

例 单链表清空

void DeleteAll(LinkList L)
{LinkList p, q;p = L->next;while(p != NULL){q = p;//记录待删点p = p->next;//p继续往后走delete q;//释放空间}L->next = NULL;//只剩头结点了，后驱置空}

例 单链表逆置

思路：

  •  对每个结点*p，将其next改指其前趋*q；
  • 修改*p的next后，将不能从*p搜索到其后继，所以修改前先     将其后继*r的位置保留起来。
  •  原首结点成为尾结点，其next应为NULL；为使该结点的处理与其它结点一致，可在算法开始时将其前趋置为NULL而不是head。
  • 头结点的next指向原尾结点。
  • void reverse(LinkList head)
{LinkList q, p, r;p = head->next;//因为 head 通常是头结点，head->next 才指向链表中第一个存有有效数据的节点q = NULL;//用q来标记p的前一个结点while (p != NULL)//用p来遍历链表{r = p->next;//用r来记录当前结点的后驱p->next = q;//把p的后驱指向前一个结点，此时p原来的后驱就丢失了,而r刚好记录q = p;//用q记录p，p继续向后走p = r;//r记录了p的后驱，此时q相当于前一个结点}
}

    例： 链表合并

将两个递增有序线性链表归并成一个非递减有序表。

原理：将两表当前结点中较小的尾插到新表

LinkList merge(LinkList A, LinkList B)
{LinkList p, q, r, head;head = new Lnode;r = head;p = A->next; q = B->next;while (p != NULL && q != NULL)//当p，q都没有到末尾时if (p->data < q->data) //如果A链表数据更小{ r->next = p; //新链表的下一个结点就是pr = p; //用r标识新链表中的 当前结点p = p->next;//A中p前进一位}else { r->next = q; //否则，B中数据大r = q;q = q->next; }if (p != NULL)  r->next = p;//如果A链表还没被遍历完，新链表直接接上A剩下的结点if (q != NULL)  r->next = q;//如果B链表还没被遍历完，新链表直接接上B剩下的结点delete A;delete B;
}

小结

  • 单链表是线性表的一种链式存储结构
  • 线性链表的特点:
  1. 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；
  2. 插入、删除操作通过修改结点的指针实现；
  3. 不能随机存取元素；

http://www.15wanjia.com/news/14393.html

相关文章：

  • 响应式网站视频营销策划公司
  • 网站建设和Java互联网运营自学课程
  • 做网站要用多少钱凡科建站手机版登录
  • 深圳响应式网站建设站长工具关键词排名怎么查
  • 建设局职责郑州网站seo优化公司
  • 做爰全过程免费的视频凤凰网站seo变现培训
  • 重庆建设安全管理网站开发app需要多少资金
  • 沈丘做网站yooker外贸接单平台
  • 公司的网站建设要记到什么科目推广新产品最好的方法
  • 网站建设入门到精通百度服务商平台
  • 上海网站建设熊掌号链接下载
  • 下载素材第三方网站是怎么做最新的全国疫情数据
  • asp网站开发需要什么制作网站费用
  • 做微信公众号用什么网站网络促销的方法有哪些
  • 网站开发报价评估巨量算数数据分析入口
  • 上海人才网招聘网最新招聘网站优化seo怎么做
  • 徐州企业网站制作seo文章代写平台
  • 网站建设 h5广州头条新闻最新
  • 单位做网站怎么做网络推广的优化服务
  • 运城建网站seo投放营销
  • 苏州百姓网免费发布信息网seo关键词是怎么优化的
  • 我要浏览国外网站怎么做深圳seo排名优化
  • b2b网站有那些网络推广是什么职业
  • 有名的软件开发公司正规seo关键词排名网络公司
  • 寮步网站仿做青岛关键词优化seo
  • 建设网站公司 优帮云三只松鼠营销案例分析
  • 国内html网站欣赏营销一体化平台
  • asp 网站权限设计郑州新闻发布
  • 深圳建设局网站宝安分中心app制作费用一览表
  • 商务部市场体系建设司网站东莞seo外包平台