一、Xmind整理：

二、课上练习：

练习1：时间复杂度

时间复杂度：只保留最高阶f(n)=3*n^2+n^2+100+nT(n)=O(3*n^3+n^2+100+n)=O(3*n^3)=O(n^3)1>O(1):常数阶int t=a; 1a=b;    1a=t;    1f(n)=3T(n)=O(3)=O(3*n^0)=O(n^0)=O(1)2>O(n): 线性阶for(int i=1;i<=n;i++)    n+1{printf("1");          n}f(n)=n*2+1=n3> O(n^2): 平方阶for(int i=1;i<=n;i++)    n+1{for(int j=1;j<=n;j++) n*(n+1){printf("1");        n*n}    }f(n)=2*n^2+2*n+1--->n^2for(int i=1;i<n;i++)  n{for(int j=0;j<n-i;j++) (n-1)*(n-i){printf("1");        (n-1)*(n-i-1)}    }f(n)=n^24> O(n^3): 立方阶for(int i=1;i<=n;i++) n+1{for(int j=1;j<=m;j++) n*(m+1){for(int k=1;k<=n;k++) n*m*(n+1){printf("1");       n*m*n         }            }}f(n)=2*n^2*m+2*n*m+1=2*n^2*m=n^2*m5>O(log2n):对数阶int i=1;   1int n=8;   1while(i<n) log2 n +1{i*=3;    123   log2 n}f(n)=2*log2 n  +3=log2n

三、课后作业：

1.顺序表按下标/数据元素实现增、删、改、查

head.h

//预处理命令
//函数声明
//全局变量
#ifndef __HEAD_H__
#define __HEAD_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 8
typedef int datatype;
//定义顺序表
typedef struct
{//顺序表长度int len;//数据元素datatype data[MAXSIZE];
}Seqlist;
Seqlist *create_list();
int full_list(Seqlist *list);
int insert_rear(datatype e,Seqlist *list);
int empty(Seqlist *list);
void output(Seqlist *list);
int delete_rear(Seqlist *list);
datatype search_by_sub(int sub,Seqlist *list);
int update_by_sub(Seqlist *list,int sub,datatype e);
int insert_by_sub(Seqlist *list,int sub,datatype e);
int delete_by_sub(Seqlist *list,int sub);
int search_by_data(datatype key,Seqlist *list);
int update_by_data(datatype key,datatype e,Seqlist *list);
int insert_by_data(datatype key,datatype e,Seqlist *list);
int delete_by_data(datatype key,Seqlist *list);
#endif

test.c 

//写自定义函数
#include "head.h"
/** function:    顺序表在堆区申请空间* @param [ in] * @param [out] * @return      */
Seqlist *create_list()
{Seqlist *list=(Seqlist *)malloc(sizeof(Seqlist));if(NULL==list){return NULL;}list->len=0; //顺序表长度清零memset(list->data,0,sizeof(list->data));
}
/** function:    判断顺序表满* @param [ in] * @param [out] * @return      满返回-1　不满返回0*/		
int full_list(Seqlist *list)
{return list->len==MAXSIZE?-1:0;
}
/** function:    尾插，插入一个* @param [ in] * @param [out] * @return      成功返回0　失败返回-1*/
int insert_rear(datatype e,Seqlist *list)
{if(NULL==list||full_list(list)){printf("insert rear error\n");return -1;}list->data[list->len]=e;list->len++;return 0;
}
/** function:    顺序表为空* @param [ in] * @param [out] * @return      空返回-1 非空返回0*/
int empty(Seqlist *list)
{return list->len==0?-1:0;
}
/** function:    输出* @param [ in] * @param [out] * @return      */
void output(Seqlist *list)
{if(NULL==list||empty(list)){puts("output error");return;}for(int i=0;i<list->len;i++){printf("%d\t",list->data[i]);}puts("");
}
/** function:    尾部删除* @param [ in] * @param [out] * @return      成功返回0 失败返回-1*/
int delete_rear(Seqlist *list)
{if(NULL==list||empty(list)){puts("delete rear error");return -1;}printf("delete element is:%d\n",list->data[list->len+1]);list->len--;
}
/** function:    按下标查找* @param [ in] * @param [out] * @return      成功返回查找的值　失败返回-1*/
datatype search_by_sub(int sub,Seqlist *list)
{//1.判断顺序表是否存在//2.判断顺序表是否为空//3.判断下标是否合法if(NULL==list||empty(list)||sub<0||sub>=list->len){puts("search element error");return -1;}return list->data[sub];
}
/** function:    按下标修改* @param [ in] * @param [out] * @return      成功返回0　失败返回-1*/
int update_by_sub(Seqlist *list,int sub,datatype e)
{if(NULL==list||empty(list)||sub<0||sub>=list->len){return -1;}list->data[sub]=e;return 0;
}
/** function:    按下标插入* @param [ in] * @param [out] * @return      成功返回0 失败返回-1*/
int insert_by_sub(Seqlist *list,int sub,datatype e)
{if(NULL==list||full_list(list)||sub<0||sub>list->len){printf("insert error\n");return -1;}for(int i=list->len-1;i>=sub;i--){list->data[i+1]=list->data[i];}list->data[sub]=e;list->len++;return 0;
}
/** function:    按下标删除* @param [ in] * @param [out] * @return      成功返回0 失败返回-1*/
int delete_by_sub(Seqlist *list,int sub)
{if(NULL==list||empty(list)||sub<0||sub>=list->len){printf("delete error\n");return -1;}for(int i=sub;i<=list->len-1;i++){list->data[i]=list->data[i+1];}list->len--;return 0;
}
/** function:  按元素查找* @param [ in] * @param [out] * @return      成功返回元素下标 失败返回-1*/
int search_by_data(datatype key,Seqlist *list)
{//1.判断顺序表是否存在//2.判断顺序表是否为空if(NULL==list||empty(list)){return -1;}//3.按元素查找for(int i=0;i<list->len;i++){if(key==list->data[i]){return i;}}return -1;
}
/** function:    按元素修改* @param [ in] * @param [out] * @return      成功返回0 失败返回-1*/
int update_by_data(datatype key,datatype e,Seqlist *list)
{int sub=search_by_data(key,list);if(sub==-1){printf("update error\n");}list->data[sub]=e;return 0;
}
/** function:    按元素插入* @param [ in] * @param [out] * @return      成功返回0 失败返回-1*/
int insert_by_data(datatype key,datatype e,Seqlist *list)
{int sub=search_by_data(key,list);if(sub==-1)return -1;insert_by_sub(list,sub,e);return 0;
}
/** function:    按元素删除* @param [ in] * @param [out] * @return      成功返回0 失败返回-1*/
int delete_by_data(datatype key,Seqlist *list)
{int sub=search_by_data(key,list);if(sub==-1){printf("delete error\n");}delete_by_sub(list,sub);
}

main.c 

//写主函数
#include "head.h"
int main(int argc, const char *argv[])
{Seqlist *list=create_list();int n;printf("please enter n:");scanf("%d",&n);datatype e;//表示插入的值for(int i=0;i<n;i++){printf("please enter rear element:");scanf("%d",&e);insert_rear(e,list);}output(list);delete_rear(list);output(list);	//按下标查找int sub;printf("please search sub:");scanf("%d",&sub);e=search_by_sub(sub,list);if(e!=-1){printf("search element is:%d\n",e);}//按下标修改printf("please update sub:");scanf("%d",&sub);printf("please enter update element: ");scanf("%d",&e);update_by_sub(list,sub,e);output(list);//按下标插入printf("please insert sub:");scanf("%d",&sub);printf("please enter insert element:");scanf("%d",&e);insert_by_sub(list,sub,e);output(list);//按下标删除printf("please delete sub:");scanf("%d",&sub);delete_by_sub(list,sub);output(list);//按元素查找datatype key;printf("please enter search key:");scanf("%d",&key);int key_sub=search_by_data(key,list);if(key_sub==-1)puts("search error\n");elseprintf("find in %d\n",key_sub);//按元素修改printf("please enter update key:");scanf("%d",&key);printf("please enter update element: ");scanf("%d",&e);update_by_data(key,e,list);output(list);//按元素插入printf("please enter insert key:");scanf("%d",&key);printf("please enter insert element:");scanf("%d",&e);insert_by_data(key,e,list);output(list);//按元素删除printf("please enter delete key:");scanf("%d",&key);delete_by_data(key,list);output(list);return 0;
}